Computing the pathwidth of directed graphs with small vertex cover
From MaRDI portal
Publication:477674
DOI10.1016/J.IPL.2014.10.002zbMATH Open1304.05061OpenAlexW2052101592MaRDI QIDQ477674FDOQ477674
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
Recommendations
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)
Cites Work
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A note on exact algorithms for vertex ordering problems on graphs
- Directed path-width and monotonicity in digraph searching
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Computing Directed Pathwidth in O(1.89 n ) Time
- Title not available (Why is that?)
- The vertex separation number of a graph equals its path-width
- Computing Pathwidth Faster Than 2 n
- Linear layouts in submodular systems
- Digraph searching, directed vertex separation and directed pathwidth
- Treewidth and Pathwidth Parameterized by the Vertex Cover Number
Cited In (7)
- Computing directed Steiner path covers for directed co-graphs (extended abstract)
- Computing directed pathwidth in \(O(1.89^n)\) time
- 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
- Computing Directed Pathwidth in O(1.89 n ) Time
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)
