Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
From MaRDI portal
Publication:5266611
DOI10.1145/2851494zbMath1365.90273OpenAlexW2286129431MaRDI QIDQ5266611
Nicolas Nisse, David Coudert, Dorian Mazauric
Publication date: 16 June 2017
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01266496/file/babpw-20151120.pdf
Nonnumerical algorithms (68W05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ Unnamed Item ⋮ Finding small-width connected path decompositions in polynomial time
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Variable neighborhood search for the vertex separation problem
- The dag-width of directed graphs
- Treewidth computations. II. Lower bounds
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Monadic second-order evaluations on tree-decomposable graphs
- A note on exact algorithms for vertex ordering problems on graphs
- Digraph measures: Kelly decompositions, games, and orderings
- Digraph searching, directed vertex separation and directed pathwidth
- Monotonicity in digraph search problems
- Treewidth computations. I: Upper bounds
- On the maximum cardinality search lower bound for treewidth
- On problems without polynomial kernels
- Graph minors. I. Excluding a forest
- Min Cut is NP-complete for edge weighted trees
- The vertex separation number of a graph equals its path-width
- A partial k-arboretum of graphs with bounded treewidth
- On the pathwidth of chordal graphs
- Call routing and the ratcatcher
- Searching and pebbling
- Directed tree-width
- Characterization of graphs and digraphs with small process numbers
- Directed path-width and monotonicity in digraph searching
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings
- Kernel Bounds for Structural Parameterizations of Pathwidth
- Pathwidth of Circular-Arc Graphs
- Improved approximation algorithms for minimum-weight vertex separators
- Computing Pathwidth Faster Than 2 n
- Graph minors. II. Algorithmic aspects of tree-width
- The complexity of searching a graph
- Monotonicity in graph searching
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
- The Pathwidth and Treewidth of Cographs
- Treewidth and Pathwidth of Permutation Graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Computing Directed Pathwidth in O(1.89 n ) Time
- Theory and Applications of Satisfiability Testing
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- On Exact Algorithms for Treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Experimental and Efficient Algorithms
- Principles and Practice of Constraint Programming – CP 2004
This page was built for publication: Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
