Computing directed pathwidth in \(O(1.89^n)\) time
From MaRDI portal
Publication:300464
DOI10.1007/s00453-015-0015-9zbMath1339.05392OpenAlexW2344397418MaRDI QIDQ300464
Hisao Tamaki, Kenta Kitsunai, Yasuaki Kobayashi, Toshihiro Tano, Keita Komuro
Publication date: 28 June 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0015-9
Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Characterizations and directed path-width of sequence digraphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ Comparing linear width parameters for directed graphs ⋮ Digraphs of Bounded Width
Cites Work
- Unnamed Item
- Exact exponential algorithms.
- A note on exact algorithms for vertex ordering problems on graphs
- Digraph searching, directed vertex separation and directed pathwidth
- Graph minors. I. Excluding a forest
- Min Cut is NP-complete for edge weighted trees
- The vertex separation number of a graph equals its path-width
- On the pathwidth of chordal graphs
- Treewidth of cocomparability graphs and a new order-theoretic parameter
- Directed tree-width
- Graph minors. XIII: The disjoint paths problem
- Directed path-width and monotonicity in digraph searching
- Computing Tree-Depth Faster Than 2 n
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Finding Induced Subgraphs via Minimal Triangulations
- Pathwidth of Circular-Arc Graphs
- Computing Pathwidth Faster Than 2 n
- The Pathwidth and Treewidth of Cographs
- Treewidth and Pathwidth of Permutation Graphs
- Computing Directed Pathwidth in O(1.89 n ) Time
- Linear Layouts in Submodular Systems
- Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Computing directed pathwidth in \(O(1.89^n)\) time
