Name
Abstract | ||
|---|---|---|
In this paper, we consider the problem of computing an optimal branch decomposition of a graph. Branch decompositions and
branchwidth were introduced by Robertson and Seymour in their series of papers that proved the Graph Minors Theorem. Branch
decompositions have proven to be useful in solving many NP-hard problems, such as the traveling salesman, independent set,
and ring routing problems, by means of combinatorial algorithms that operate on branch decompositions. We develop an implicit
enumeration algorithm for the optimal branch decomposition problem and examine its performance on a set of classical graph
instances. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10589-011-9397-z | Computational Optimization and Applications |
Keywords | Field | DocType |
Branch decomposition,Branchwidth,Implicit enumeration,Partitioning | Bottleneck traveling salesman problem,Discrete mathematics,Mathematical optimization,Branch and bound,Combinatorics,Branch and cut,Branch and price,Combinatorial optimization,Travelling salesman problem,Optimization problem,Mathematics,Branch-decomposition | Journal |
Volume | Issue | ISSN |
51 | 3 | 0926-6003 |
Citations | PageRank | References |
2 | 0.37 | 13 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Cole Smith | 1 | 610 | 43.34 |
| Elif Ulusal | 2 | 2 | 0.71 |
| Illya V. Hicks | 3 | 221 | 18.81 |