A Polynomial Time Algorithm for Bounded Directed Pathwidth
From MaRDI portal
Recommendations
- Algorithms for solving problems on graphs of bounded pathwidth
- Computing directed pathwidth in O(1.89ⁿ) time
- Computing Directed Pathwidth in O(1.89 n ) Time
- A New Polynomially Bounded Shortest Path Algorithm
- A linear fixed parameter tractable algorithm for connected pathwidth
- scientific article; zbMATH DE number 7651203
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- A polynomial-time algorithm to find shortest paths with recourse
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Paths of bounded length and their cuts: parameterized complexity and algorithms
Cites work
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Complexity of Finding Embeddings in a k-Tree
- DAG-Width and Parity Games
- DAG-width
- Digraph measures: Kelly decompositions, games, and orderings
- Digraph searching, directed vertex separation and directed pathwidth
- Directed path-width and monotonicity in digraph searching
- Directed tree-width
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Graph minors. I. Excluding a forest
- Graph minors. III. Planar tree-width
- Graph minors. XX: Wagner's conjecture
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Mathematical Foundations of Computer Science 2005
- On digraph width measures in parameterized algorithmics
- On the Algorithmic Effectiveness of Digraph Decompositions and Complexity Measures
- The vertex separation number of a graph equals its path-width
Cited in
(16)- Computing Directed Pathwidth in O(1.89 n ) Time
- On the complexity of the FIFO stack-up problem
- Computing the zig-zag number of directed graphs
- A tight amortized bound for path reversal
- Computing directed pathwidth in O(1.89ⁿ) time
- Characterizations and directed path-width of sequence digraphs
- On the pathwidth of almost semicomplete digraphs
- Comparing linear width parameters for directed graphs
- Directed path-width of sequence digraphs
- Bipartite independent set reconfiguration: general and RNA-inspired parameterized algorithms
- Computing the pathwidth of directed graphs with small vertex cover
- How to compute digraph width measures on directed co-graphs
- Using decomposition-parameters for QBF: mind the prefix!
- Digraphs of bounded width
- A slice theoretic approach for embedding problems on digraphs
- Directed pathwidth and palletizers
This page was built for publication: A Polynomial Time Algorithm for Bounded Directed Pathwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3104788)
