Graph minors. II. Algorithmic aspects of tree-width

Neil Robertson, P. D. Seymour

Research output: Contribution to journalArticle

994 Scopus citations

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 languageEnglish (US)
Pages (from-to)309-322
Number of pages14
JournalJournal of Algorithms
Volume7
Issue number3
DOIs
StatePublished - Sep 1986
Externally publishedYes

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