On the Pathwidth of Almost Semicomplete Digraphs
From MaRDI portal
Publication:3452843
DOI10.1007/978-3-662-48350-3_68zbMath1466.05081arXiv1507.01934MaRDI QIDQ3452843
Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki
Publication date: 19 November 2015
Published in: Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1507.01934
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
Related Items
Characterizations and directed path-width of sequence digraphs, How to compute digraph width measures on directed co-graphs, On width measures and topological problems on semi-complete digraphs, Comparing linear width parameters for directed graphs, On the Pathwidth of Almost Semicomplete Digraphs
Cites Work
- Unnamed Item
- Edge-disjoint paths in digraphs with bounded independence number
- Disjoint paths in tournaments
- A well-quasi-order for tournaments
- Graph minors. XX: Wagner's conjecture
- Tournament pathwidth and topological containment
- Digraph searching, directed vertex separation and directed pathwidth
- The directed subgraph homeomorphism problem
- Graph minors. XIII: The disjoint paths problem
- Tournament minors
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- On the Pathwidth of Almost Semicomplete Digraphs
- Linear Layouts in Submodular Systems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth