절단 폭

Cutwidth
Stub icon

이 콤비네이터 관련 기사는 스텁입니다.위키피디아를 확장함으로써 위키피디아를 도울 수 있습니다.


그래프 이론에서, 무방향 그래프 G = (V, E)의 절단 폭은 다음과 같은 성질을 가진 가장 작은 정수 k이다: 모든 l = 1, …, nn – 1에 대해 {v11l + 1, …, vl}에n [1]끝점이 하나 있는 최대 k개의 가장자리가 있다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a Tree". SIAM Journal on Algebraic and Discrete Methods. 6 (2): 268–277. doi:10.1137/0606026. ISSN 0196-5212.
  2. ^ Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm". Journal of Algorithms. 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. ISSN 0196-6774.