𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Directed Tree-Width

✍ Scribed by Thor Johnson; Neil Robertson; P.D. Seymour; Robin Thomas

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
198 KB
Volume
82
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Tree-width and circumference of graphs
Tree-width and circumference of graphs
✍ Etienne Birmele πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 37 KB

## Abstract We prove that every graph of circumference __k__ has tree‐width at most __k__β€‰βˆ’β€‰1 and that this bound is best possible. Β© 2003 Wiley Periodicals, Inc. J Graph Theory 43: 24–25, 2003

Surfaces, Tree-Width, Clique-Minors, and
Surfaces, Tree-Width, Clique-Minors, and Partitions
✍ Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 214 KB

In 1971, Chartrand, Geller, and Hedetniemi conjectured that the edge set of a planar graph may be partitioned into two subsets, each of which induces an outerplanar graph. Some partial results towards this conjecture are presented. One such result, in which a planar graph may be thus edge partitione

Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
✍ Jens Lagergren πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem Ε½ 3 . Ε½. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-Ε½ 2 . position algorithm is O O n log n . The tree-decomposi

Optimal Parametric Search on Graphs of B
Optimal Parametric Search on Graphs of Bounded Tree-Width
✍ David FernΓ‘ndez-Baca; Giora Slutzki πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 339 KB

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.

Ka,k Minors in Graphs of Bounded Tree-Wi
Ka,k Minors in Graphs of Bounded Tree-Width
✍ Thomas BΓΆhme; John Maharry; Bojan Mohar πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 175 KB

It is shown that for any positive integers k and w there exists a constant N ¼ N ðk; wÞ such that every 7-connected graph of tree-width less than w and of order at least N contains K 3;k as a minor. Similar result is proved for K a;k minors where a is an arbitrary fixed integer and the required conn

Complexes of Directed Trees
Complexes of Directed Trees
✍ Dmitry N. Kozlov πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 153 KB

To every directed graph G one can associate a complex 2(G) consisting of directed subforests. This construction, suggested to us by R. Stanley, is especially important in the case of a complete double directed graph G n , where it leads to the study of some interesting representations of the symmetr