Computing directed pathwidth in O(1.89ⁿ) time

DOI10.1007/S00453-015-0015-9MaRDI QIDQ300464zbMATH OpenOpenAlexFDO

Authors Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano

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

exact exponential algorithmgraph algorithmpathwidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12)

Recommendations

• Computing Directed Pathwidth in O(1.89 n ) Time
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Computing the pathwidth of directed graphs with small vertex cover
• Computing Pathwidth Faster Than 2 n
• Characterizations and directed path-width of sequence digraphs

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• A note on exact algorithms for vertex ordering problems on graphs
• Computing Directed Pathwidth in O(1.89 n ) Time
• Computing Pathwidth Faster Than 2 n
• Computing Tree-Depth Faster Than 2 n
• Digraph searching, directed vertex separation and directed pathwidth
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Exact exponential algorithms.
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• Finding induced subgraphs via minimal triangulations
• Graph minors. I. Excluding a forest
• Graph minors. XIII: The disjoint paths problem
• Linear layouts in submodular systems
• Min Cut is NP-complete for edge weighted trees
• On the pathwidth of chordal graphs
• Pathwidth of Circular-Arc Graphs
• The Pathwidth and Treewidth of Cographs
• The vertex separation number of a graph equals its path-width
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter

Cited in

(11)

• Computing Directed Pathwidth in O(1.89 n ) Time
• Computing Pathwidth Faster Than 2 n
• Characterizations and directed path-width of sequence digraphs
• Comparing linear width parameters for directed graphs
• Directed path-width of sequence digraphs
• Directed path-width and directed tree-width of directed co-graphs
• Computing the pathwidth of directed graphs with small vertex cover
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• How to compute digraph width measures on directed co-graphs
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Digraphs of bounded width

This page was built for publication: Computing directed pathwidth in \(O(1.89^n)\) time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q300464)