A combinatorial optimization algorithm for solving the branchwidth problem

A combinatorial optimization algorithm for solving the branchwidth problem

0.00 Avg rating0 Votes
Article ID: iaor20122506
Volume: 51
Issue: 3
Start Page Number: 1211
End Page Number: 1229
Publication Date: Apr 2012
Journal: Computational Optimization and Applications
Authors: , ,
Keywords: graphs, heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.