Computing the pathwidth of directed graphs with small vertex cover

DOI10.1016/J.IPL.2014.10.002MaRDI QIDQ477674zbMATH OpenOpenAlexFDO

Authors Yasuaki Kobayashi

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.10.002

zbMATH Keywords

graph algorithmspathwidthvertex coverfixed parameter tractablevertex separation

Mathematics Subject Classification ID

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

Recommendations

• Computing Directed Pathwidth in O(1.89 n ) Time
• Computing directed pathwidth in O(1.89ⁿ) time
• Computing Pathwidth Faster Than 2 n
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth

Cites work

• scientific article; zbMATH DE number 1161563 (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
• Digraph searching, directed vertex separation and directed pathwidth
• Directed path-width and monotonicity in digraph searching
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Linear layouts in submodular systems
• The vertex separation number of a graph equals its path-width
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number

Cited in

(7)

• Computing Directed Pathwidth in O(1.89 n ) Time
• Computing directed pathwidth in O(1.89ⁿ) time
• Computing directed Steiner path covers for directed co-graphs (extended abstract)
• Characterizations and directed path-width of sequence digraphs
• Comparing linear width parameters for directed graphs
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• How to compute digraph width measures on directed co-graphs

This page was built for publication: Computing the pathwidth of directed graphs with small vertex cover

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