Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
From MaRDI portal
Publication:5266611
Recommendations
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 176249 (Why is no real title available?)
- scientific article; zbMATH DE number 1303600 (Why is no real title available?)
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A \(c^k n\) 5-approximation algorithm for treewidth
- A note on exact algorithms for vertex ordering problems on graphs
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- Characterization of graphs and digraphs with small process numbers
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Computing Directed Pathwidth in O(1.89 n ) Time
- Computing Pathwidth Faster Than 2 n
- Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
- 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
- Experimental and Efficient Algorithms
- Graph minors. I. Excluding a forest
- Graph minors. II. Algorithmic aspects of tree-width
- Improved approximation algorithms for minimum-weight vertex separators
- Kernel bounds for structural parameterizations of pathwidth
- Min Cut is NP-complete for edge weighted trees
- Monadic second-order evaluations on tree-decomposable graphs
- Monotonicity in digraph search problems
- Monotonicity in graph searching
- On Exact Algorithms for Treewidth
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- On problems without polynomial kernels
- On the maximum cardinality search lower bound for treewidth
- On the pathwidth of chordal graphs
- Pathwidth of Circular-Arc Graphs
- Principles and Practice of Constraint Programming – CP 2004
- Searching and pebbling
- The Pathwidth and Treewidth of Cographs
- The complexity of searching a graph
- The dag-width of directed graphs
- The vertex separation number of a graph equals its path-width
- Theory and Applications of Satisfiability Testing
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Treewidth and Pathwidth of Permutation Graphs
- Treewidth computations. I: Upper bounds
- Treewidth computations. II. Lower bounds
- Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings
- Variable neighborhood search for the vertex separation problem
Cited in
(11)- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Graph and string parameters: connections between pathwidth, cutwidth and the locality number
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- A bound on the pathwidth of sparse graphs with applications to exact algorithms
- Faster computation of path-width
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Finding small-width connected path decompositions in polynomial time
- Computing Directed Pathwidth in O(1.89 n ) Time
- Mathematical Foundations of Computer Science 2005
- Computing directed pathwidth in \(O(1.89^n)\) time
- Computing the pathwidth of directed graphs with small vertex cover
This page was built for publication: Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5266611)
