Computing the pathwidth of directed graphs with small vertex cover

DOI10.1016/j.ipl.2014.10.002zbMath1304.05061OpenAlexW2052101592MaRDI QIDQ477674

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

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

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

Cites Work

• Unnamed Item
• A note on exact algorithms for vertex ordering problems on graphs
• Digraph searching, directed vertex separation and directed pathwidth
• The vertex separation number of a graph equals its path-width
• Directed path-width and monotonicity in digraph searching
• Treewidth and Pathwidth Parameterized by the Vertex Cover Number
• A Polynomial Time Algorithm for Bounded Directed Pathwidth
• Computing Pathwidth Faster Than 2 n
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Computing Directed Pathwidth in O(1.89 n ) Time
• Linear Layouts in Submodular Systems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth