Forbidden directed minors and Kelly-width

DOI10.1016/j.tcs.2016.12.008zbMath1357.05142arXiv1308.5170OpenAlexW2962963980MaRDI QIDQ501668

Qiuyi Zhang, Shiva Kintali

Publication date: 9 January 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

treewidthgraph minorsforbidden minorsKelly-widthpartial \(k\)-DAGs

Mathematics Subject Classification ID

Trees (05C05) Graph minors (05C83) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

Cut-sufficient directed 2-commodity multiflow topologies ⋮ Unnamed Item ⋮ Forbidden directed minors and Kelly-width ⋮ Digraphs of Bounded Width

Cites Work

• Unnamed Item
• DAG-width is PSPACE-complete
• The dag-width of directed graphs
• Forbidden directed minors and Kelly-width
• A well-quasi-order for tournaments
• Graph minors. XX: Wagner's conjecture
• Forbidden minors characterization of partial 3-trees
• Digraph measures: Kelly decompositions, games, and orderings
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Recognizing digraphs of Kelly-width 2
• Graph minors. I. Excluding a forest
• The directed subgraph homeomorphism problem
• Obstruction set isolation for the gate matrix layout problem
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• Tournament minors
• Directed path-width and monotonicity in digraph searching
• A characterization of partial 3-trees
• DAG-width
• Elimination Structures for Unsymmetric Sparse $LU$ Factors
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Forbidden directed minors and Kelly-width