The pathwidth of a graph , 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 .

As summarized in the table below, obstruction sets for pathwidth (consisting of the triangle graph and spoke graph , illustrated above) and (consisting of 110 graphs) were described in Kinnersley and Langston (1992) taking advantage of the fact that gate matrix layout with parameter is identical to the pathwidth problem with parameter (Fellows and Langston 1989, Kinnersley and Langston 1992).

The set of 110 forbidden minors (Kinnersley and Langston 1992) is illustrated above. They are implemented in the Wolfram Language as GraphData["PathwidthForbidden"].

See also

Graph Bandwidth, Spoke Graph, 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.

Referenced on Wolfram|Alpha

Pathwidth

Cite this as:

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

Subject classifications