Directed tree-width

Thor Johnson, Neil Robertson, P. D. Seymour, Robin Thomas

Research output: Contribution to journalArticlepeer-review

177 Scopus citations

Abstract

We generalize the concept of tree-width to directed graphs and prove that every directed graph with no "haven" of large order has small tree-width. Conversely, a digraph with a large haven has large tree-width. We also show that the Hamilton cycle problem and other NP-hard problems can be solved in polynomial time when restricted to digraphs of bounded tree-width.

Original languageEnglish (US)
Pages (from-to)138-154
Number of pages17
JournalJournal of Combinatorial Theory. Series B
Volume82
Issue number1
DOIs
StatePublished - May 1 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Directed tree-width'. Together they form a unique fingerprint.

Cite this