TY - JOUR

T1 - Graph minors. II. Algorithmic aspects of tree-width

AU - Robertson, Neil

AU - Seymour, P. D.

N1 - Funding Information:
*Research partially supported by NSF Grant MCS 8103440. Present address: Bell Communications Research. Inc., Morris Research and Engineering Center, 435 South Street, Morristown, New Jersey 07960.

PY - 1986/9

Y1 - 1986/9

N2 - We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width ≤ w, for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width.

AB - We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width ≤ w, for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width.

UR - http://www.scopus.com/inward/record.url?scp=0000673493&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000673493&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(86)90023-4

DO - 10.1016/0196-6774(86)90023-4

M3 - Article

AN - SCOPUS:0000673493

SN - 0196-6774

VL - 7

SP - 309

EP - 322

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 3

ER -