Directed Minors III. Directed Linked Decompositions

2014/04/23 by Shiva Kintali, Kintali, Shiva
#math.CO

paper · pdf · doi:10.48550/arxiv.1404.5976

Abstract

Thomas proved that every undirected graph admits a linked tree decomposition of width equal to its treewidth. In this paper, we generalize Thomas's theorem to digraphs. We prove that every digraph G admits a linked directed path decomposition and a linked DAG decomposition of width equal to its directed pathwidth and DAG-width respectively.

Related

• Directed path-decompositions
• A unified treatment of linked and lean tree-decompositions
• On tree decompositions whose trees are minors
• Non-branching tree-decompositions
• The canonical directed tree decomposition and its applications to the directed disjoint paths problem