Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
DOI10.1145/2851494zbMATH Open1365.90273OpenAlexW2286129431MaRDI QIDQ5266611FDOQ5266611
Authors: David Coudert, Dorian Mazauric, Nicolas Nisse 
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
Recommendations
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Nonnumerical algorithms (68W05)
Cites Work
- Theory and Applications of Satisfiability Testing
- Title not available (Why is that?)
- 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
- On problems without polynomial kernels
- Min Cut is NP-complete for edge weighted trees
- A partial k-arboretum of graphs with bounded treewidth
- Call routing and the ratcatcher
- Searching and pebbling
- Directed tree-width
- Directed path-width and monotonicity in digraph searching
- The dag-width of directed graphs
- Computing Directed Pathwidth in O(1.89 n ) Time
- On Exact Algorithms for Treewidth
- Digraph measures: Kelly decompositions, games, and orderings
- Graph minors. II. Algorithmic aspects of tree-width
- The complexity of searching a graph
- Graph minors. I. Excluding a forest
- The vertex separation number of a graph equals its path-width
- On the pathwidth of chordal graphs
- Characterization of graphs and digraphs with small process numbers
- Pathwidth of Circular-Arc Graphs
- Computing Pathwidth Faster Than 2 n
- Monotonicity in graph searching
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- The Pathwidth and Treewidth of Cographs
- Treewidth and Pathwidth of Permutation Graphs
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Digraph searching, directed vertex separation and directed pathwidth
- Treewidth computations. I: Upper bounds
- Monadic second-order evaluations on tree-decomposable graphs
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Variable neighborhood search for the vertex separation problem
- Title not available (Why is that?)
- Kernel bounds for structural parameterizations of pathwidth
- Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
- Title not available (Why is that?)
- Treewidth computations. II. Lower bounds
- Improved approximation algorithms for minimum-weight vertex separators
- A \(c^k n\) 5-approximation algorithm for treewidth
- Principles and Practice of Constraint Programming – CP 2004
- On the maximum cardinality search lower bound for treewidth
- Monotonicity in digraph search problems
- Experimental and Efficient Algorithms
- A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
- Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings
Cited In (8)
- A bound on the pathwidth of sparse graphs with applications to exact algorithms
- Mathematical Foundations of Computer Science 2005
- Computing directed pathwidth in \(O(1.89^n)\) time
- Finding small-width connected path decompositions in polynomial time
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- Title not available (Why is that?)
- Computing Directed Pathwidth in O(1.89 n ) Time
Uses Software
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)
