A combinatorial optimization algorithm for solving the branchwidth problem

J. Cole Smith, Elif Ulusal, Illya V. Hicks

Research output: Contribution to journalArticle

6 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1211-1229
Number of pages19
JournalComputational Optimization and Applications
Volume51
Issue number3
DOIs
StatePublished - Apr 1 2012
Externally publishedYes

Keywords

  • Branch decomposition
  • Branchwidth
  • Implicit enumeration
  • Partitioning

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A combinatorial optimization algorithm for solving the branchwidth problem'. Together they form a unique fingerprint.

  • Cite this