Directed tree-width

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

doi:10.1006/jctb.2000.2031

Directed tree-width

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

Mathematics

Research output: Contribution to journal › Article › peer-review

230 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 language	English (US)
Pages (from-to)	138-154
Number of pages	17
Journal	Journal of Combinatorial Theory. Series B
Volume	82
Issue number	1
DOIs	https://doi.org/10.1006/jctb.2000.2031
State	Published - May 2001

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.2000.2031

Cite this

@article{ba63ef40a1c743bf944f67578249cd04,

title = "Directed tree-width",

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.",

author = "Thor Johnson and Neil Robertson and Seymour, \{P. D.\} and Robin Thomas",

note = "Funding Information: 1Partially supported by the NSF under Grant DMS-9701598. 2 Research partially supported by the DIMACS Center, Rutgers University, New Brunswick, NJ 08903. 3Partially supported by the NSF under Grant DMS-9401981. 4Partially supported by the ONR under Contact N00014-97-1-0512. 5Partially supported by the NSF under Grant DMS-9623031 and by the NSA under Contract MDA904-98-1-0517.",

year = "2001",

month = may,

doi = "10.1006/jctb.2000.2031",

language = "English (US)",

volume = "82",

pages = "138--154",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Directed tree-width

AU - Johnson, Thor

AU - Robertson, Neil

AU - Seymour, P. D.

AU - Thomas, Robin

N1 - Funding Information: 1Partially supported by the NSF under Grant DMS-9701598. 2 Research partially supported by the DIMACS Center, Rutgers University, New Brunswick, NJ 08903. 3Partially supported by the NSF under Grant DMS-9401981. 4Partially supported by the ONR under Contact N00014-97-1-0512. 5Partially supported by the NSF under Grant DMS-9623031 and by the NSA under Contract MDA904-98-1-0517.

PY - 2001/5

Y1 - 2001/5

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0035343968

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

U2 - 10.1006/jctb.2000.2031

DO - 10.1006/jctb.2000.2031

M3 - Article

AN - SCOPUS:0035343968

SN - 0095-8956

VL - 82

SP - 138

EP - 154

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 1

ER -

Directed tree-width

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this