Computing directed pathwidth in \(O(1.89^n)\) time

DOI10.1007/s00453-015-0015-9zbMath1339.05392MaRDI 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

zbMATH Keywords

graph algorithm; pathwidth; exact exponential algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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