Directed tree-width

Authors
Johnson, T Robertson, N Seymour, PD Thomas, R
Citation
T. Johnson et al., Directed tree-width, J COMB TH B, 82(1), 2001, pp. 138-154
Citations number
19
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
82
Issue
1
Year of publication
2001
Pages
138 - 154
Database
ISI
SICI code
0095-8956(200103)82:1<138:DT>2.0.ZU;2-D
Abstract
We generalize thr concept of tree-width to directed graphs and prove that e very directed graph with no "haven" of large order has small tree-width. Co nversely, a digraph with a large haven has large tree-width. We also show t hat the Hamilton cycle problem and other NP-hard problems can be solved in polynomial time when restricted to digraphs of bounded tree-width. (C) 2001 Academic Press.