On the Pathwidth of Almost Semicomplete Digraphs

DOI10.1007/978-3-662-48350-3_68zbMath1466.05081arXiv1507.01934OpenAlexW1819685437MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

On the Pathwidth of Almost Semicomplete Digraphs ⋮ 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

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

This page was built for publication: On the Pathwidth of Almost Semicomplete Digraphs