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
VL - 7
SP - 309
EP - 322
JO - Journal of Algorithms
JF - Journal of Algorithms
SN - 0196-6774
IS - 3
ER -