Cutwidth

This combinatorics-related article is a stub. You can help Justapedia by expanding it.

In graph theory, the cutwidth of an undirected graph $G = (V, E)$ is the smallest integer $k$ with the following property: there is an ordering ${v 1, \dots, v n}$ of the vertices of $G$ , such that for every $l = 1, \dots, n - 1$ , there are at most $k$ edges with one endpoint in ${v 1, \dots, v l}$ and the other endpoint in ${v l + 1, \dots, v n}$ .^[1] ^[2]

References[edit]

^ 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.
^ 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.

[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.

[1]

[2]

Cutwidth

See also[edit]

References[edit]

Navigation menu