TOPICS

Pathwidth

The pathwidth of a graph G, also called the interval thickness, vertex separation number, and node searching number, is one less than the size of the largest set in a path decomposition G.

PathwidthForbiddenMinors

Obstruction sets for pathwidth 1 and 2 were described in Kinnersley and Langston (1992) taking advantage of the fact that gate matrix layout with parameter k is identical to the pathwidth problem with parameter k-1 (Fellows and Langston 1989, Kinnersley and Langston 1992).

pathwidth boundobstruction
<=1C_3 and a 7-vertex tree
<=2110 forbidden minors

See also

Graph Bandwidth, Treewidth

Explore with Wolfram|Alpha

References

Chlebiková, J. "The Structure of Obstructions to Treewidth and Pathwidth." Disc. Appl. Math. 120, 61-71, 2002.Fellows, M. R. and Langston, M. A. "On Search, Decision and the Efficiency of Polynomial-Time Algorithms." In Proceedings of the 21st ACM Symposium on the Theory of Computing, pp. 501-512, 1989.Kinnersley, N. G. and Langston, M. A. "Obstruction Set Isolation for the Gate Matrix Layout Problem." Disc. Appl. Math. 54, 169-213, 1992.

Cite this as:

Weisstein, Eric W. "Pathwidth." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Pathwidth.html

Subject classifications