Directed Path-Decompositions

DOI10.1137/19M1248728zbMath1432.05079arXiv1711.00718OpenAlexW3006501763MaRDI QIDQ5215903

Joshua Erde

Publication date: 13 February 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1711.00718

zbMATH Keywords

tree-decompositionpath-widthlinked tree-decomposition

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Directed graphs (digraphs), tournaments (05C20)

Related Items

Tangle-tree duality in abstract separation systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithmic metatheorem for directed treewidth
• The dag-width of directed graphs
• Digraph measures: Kelly decompositions, games, and orderings
• Submodular partition functions
• A Menger-like property of tree-width: The finite case
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a forest
• Graph searching and a min-max theorem for tree-width
• A unified treatment of linked and lean tree-decompositions
• Directed tree-width
• Tangle-tree duality: in graphs, matroids and beyond
• Tournament minors
• Directed path-width and monotonicity in digraph searching
• The Directed Grid Theorem
• Unifying Duality Theorems for Width Parameters in Graphs and Matroids (Extended Abstract)
• Parameters Tied to Treewidth
• Digraphs of Bounded Width
• DAG-width
• Graph Minors I: A Short Proof of the Path-width Theorem
• Mathematical Foundations of Computer Science 2005