Cutwidth

In graph theory, the cutwidth of an undirected graph is the smallest integer with the following property: there is an ordering of the vertices of the graph, such that every cut obtained by partitioning the vertices into earlier and later subsets of the ordering is crossed by at most edges. That is, if the vertices are numbered , then for every , the number of edges with and is at most .[1]

Cutwidth is related to several other width parameters of graphs. In particular, it is always as least as large as the treewidth or pathwidth of the same graph. However, it is at most the treewidth mutiplied by where is the maximum degree and is the number of vertices.[2]

The problem of computing the cutwidth has also been called "minimum cut linear arrangement". It can be solved in time for a tree of vertices.[3] For more general graphs, it is NP-hard, but fixed-parameter tractable: for any fixed value of , it is possible to test whether a graph has cutwidth at most , and if so find an optimal vertex ordering for it, in linear time.[4]

See also

References

  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. MR 0778007.
  2. Korach, Ephraim; Solel, Nir (1993). "Tree-width, path-width, and cutwidth". Discrete Applied Mathematics. 43 (1): 97–101. doi:10.1016/0166-218X(93)90171-J. MR 1218045.
  3. Yannakakis, Mihalis (1985). "A polynomial algorithm for the min-cut linear arrangement of trees". Journal of the ACM. 32 (4): 950–988. doi:10.1145/4221.4228. MR 0810346.
  4. 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. MR 2146375.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.