Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth (Q5266611): Difference between revisions

Latest revision as of 23:35, 13 July 2024

scientific article; zbMATH DE number 6732197

Language	Label	Description	Also known as
English	Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth	scientific article; zbMATH DE number 6732197

Statements

instance of

scholarly article

0 references

title

Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth (English)

0 references

0 references

0 references

0 references

ACM Journal of Experimental Algorithmics

0 references

publication date

16 June 2017

0 references

full work available at URL

https://hal.inria.fr/hal-01266496/file/babpw-20151120.pdf

0 references

zbMATH Keywords

graph

0 references

branch-and-bound

0 references

directed pathwidth

0 references

pathwidth

0 references

vertex separation

0 references

describes a project that uses

0 references

0 references

0 references

0 references

MaRDI publication profile

0 references

cites work

Experimental and Efficient Algorithms

0 references

A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth

0 references

Directed path-width and monotonicity in digraph searching

0 references

The dag-width of directed graphs

0 references

Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings

0 references

Q4035355

0 references

Monotonicity in graph searching

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

On problems without polynomial kernels

0 references

A $c^k n$ 5-Approximation Algorithm for Treewidth

0 references

A note on exact algorithms for vertex ordering problems on graphs

0 references

On Exact Algorithms for Treewidth

0 references

Q4250226

0 references

Kernel Bounds for Structural Parameterizations of Pathwidth

0 references

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

0 references

Treewidth and Pathwidth of Permutation Graphs

0 references

On the maximum cardinality search lower bound for treewidth

0 references

Treewidth computations. I: Upper bounds

0 references

Treewidth computations. II. Lower bounds

0 references

The Pathwidth and Treewidth of Cographs

0 references

Tradeoffs in process strategy games with application in the WDM reconfiguration problem

0 references

Characterization of graphs and digraphs with small process numbers

0 references

Monadic second-order evaluations on tree-decomposable graphs

0 references

Variable neighborhood search for the vertex separation problem

0 references

Theory and Applications of Satisfiability Testing

0 references

Q3267900

0 references

Improved approximation algorithms for minimum-weight vertex separators

0 references

On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design

0 references

Principles and Practice of Constraint Programming – CP 2004

0 references

On the pathwidth of chordal graphs

0 references

Digraph measures: Kelly decompositions, games, and orderings

0 references

Directed tree-width

0 references

The vertex separation number of a graph equals its path-width

0 references

Searching and pebbling

0 references

Computing Directed Pathwidth in O(1.89 n ) Time

0 references

The complexity of searching a graph

0 references

Min Cut is NP-complete for edge weighted trees

0 references

Graph minors. I. Excluding a forest

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Combining intensification and diversification strategies in VNS. An application to the vertex separation problem

0 references

Call routing and the ratcatcher

0 references

Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time

0 references

Pathwidth of Circular-Arc Graphs

0 references

Computing Pathwidth Faster Than 2 n

0 references

Digraph searching, directed vertex separation and directed pathwidth

0 references

Monotonicity in digraph search problems

0 references

Identifiers

zbMATH Open document ID

1365.90273

0 references

DOI

10.1145/2851494

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5266611

@@ Property / cites work @@
+Experimental and Efficient Algorithms
@@ Property / cites work: Experimental and Efficient Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
+Normal rank
@@ Property / cites work @@
+Directed path-width and monotonicity in digraph searching
+Normal rank
@@ Property / cites work @@
+The dag-width of directed graphs
@@ Property / cites work: The dag-width of directed graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings
+Normal rank
@@ Property / cites work @@
+Q4035355
@@ Property / cites work: Q4035355 / rank @@
+Normal rank
@@ Property / cites work @@
+Monotonicity in graph searching
@@ Property / cites work: Monotonicity in graph searching / rank @@
+Normal rank
@@ Property / cites work @@
+A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+On problems without polynomial kernels
@@ Property / cites work: On problems without polynomial kernels / rank @@
+Normal rank
@@ Property / cites work @@
+A $c^k n$ 5-Approximation Algorithm for Treewidth
@@ Property / cites work: A $c^k n$ 5-Approximation Algorithm for Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+A note on exact algorithms for vertex ordering problems on graphs
+Normal rank
@@ Property / cites work @@
+On Exact Algorithms for Treewidth
@@ Property / cites work: On Exact Algorithms for Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Q4250226
@@ Property / cites work: Q4250226 / rank @@
+Normal rank
@@ Property / cites work @@
+Kernel Bounds for Structural Parameterizations of Pathwidth
+Normal rank
@@ Property / cites work @@
+Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
+Normal rank
@@ Property / cites work @@
+Treewidth and Pathwidth of Permutation Graphs
@@ Property / cites work: Treewidth and Pathwidth of Permutation Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the maximum cardinality search lower bound for treewidth
+Normal rank
@@ Property / cites work @@
+Treewidth computations. I: Upper bounds
@@ Property / cites work: Treewidth computations. I: Upper bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Treewidth computations. II. Lower bounds
@@ Property / cites work: Treewidth computations. II. Lower bounds / rank @@
+Normal rank
@@ Property / cites work @@
+The Pathwidth and Treewidth of Cographs
@@ Property / cites work: The Pathwidth and Treewidth of Cographs / rank @@
+Normal rank
@@ Property / cites work @@
+Tradeoffs in process strategy games with application in the WDM reconfiguration problem
+Normal rank
@@ Property / cites work @@
+Characterization of graphs and digraphs with small process numbers
+Normal rank
@@ Property / cites work @@
+Monadic second-order evaluations on tree-decomposable graphs
+Normal rank
@@ Property / cites work @@
+Variable neighborhood search for the vertex separation problem
+Normal rank
@@ Property / cites work @@
+Theory and Applications of Satisfiability Testing
@@ Property / cites work: Theory and Applications of Satisfiability Testing / rank @@
+Normal rank
@@ Property / cites work @@
+Q3267900
@@ Property / cites work: Q3267900 / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for minimum-weight vertex separators
+Normal rank
@@ Property / cites work @@
+On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
+Normal rank
@@ Property / cites work @@
+Principles and Practice of Constraint Programming – CP 2004
+Normal rank
@@ Property / cites work @@
+On the pathwidth of chordal graphs
@@ Property / cites work: On the pathwidth of chordal graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Digraph measures: Kelly decompositions, games, and orderings
+Normal rank
@@ Property / cites work @@
+Directed tree-width
@@ Property / cites work: Directed tree-width / rank @@
+Normal rank
@@ Property / cites work @@
+The vertex separation number of a graph equals its path-width
+Normal rank
@@ Property / cites work @@
+Searching and pebbling
@@ Property / cites work: Searching and pebbling / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Directed Pathwidth in O(1.89 n ) Time
@@ Property / cites work: Computing Directed Pathwidth in O(1.89 n ) Time / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of searching a graph
@@ Property / cites work: The complexity of searching a graph / rank @@
+Normal rank
@@ Property / cites work @@
+Min Cut is NP-complete for edge weighted trees
@@ Property / cites work: Min Cut is NP-complete for edge weighted trees / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. I. Excluding a forest
@@ Property / cites work: Graph minors. I. Excluding a forest / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
+Normal rank
@@ Property / cites work @@
+Call routing and the ratcatcher
@@ Property / cites work: Call routing and the ratcatcher / rank @@
+Normal rank
@@ Property / cites work @@
+Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
+Normal rank
@@ Property / cites work @@
+Pathwidth of Circular-Arc Graphs
@@ Property / cites work: Pathwidth of Circular-Arc Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Pathwidth Faster Than 2 n
@@ Property / cites work: Computing Pathwidth Faster Than 2 n / rank @@
+Normal rank
@@ Property / cites work @@
+Digraph searching, directed vertex separation and directed pathwidth
+Normal rank
@@ Property / cites work @@
+Monotonicity in digraph search problems
@@ Property / cites work: Monotonicity in digraph search problems / rank @@
+Normal rank