Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 309-322 |
| Number of pages | 14 |
| Journal | Journal of Algorithms |
| Volume | 7 |
| Issue number | 3 |
| DOIs | |
| State | Published - Sep 1986 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics
Fingerprint Dive into the research topics of 'Graph minors. II. Algorithmic aspects of tree-width'. Together they form a unique fingerprint.
Cite this
Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309-322. https://doi.org/10.1016/0196-6774(86)90023-4