A combinatorial optimization algorithm for solving the branchwidth problem

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

doi:10.1007/s10589-011-9397-z

A combinatorial optimization algorithm for solving the branchwidth problem

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

Research output: Contribution to journal › Article › peer-review

7 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 language	English (US)
Pages (from-to)	1211-1229
Number of pages	19
Journal	Computational Optimization and Applications
Volume	51
Issue number	3
DOIs	https://doi.org/10.1007/s10589-011-9397-z
State	Published - Apr 2012
Externally published	Yes

Keywords

Branch decomposition
Branchwidth
Implicit enumeration
Partitioning

ASJC Scopus subject areas

Control and Optimization
Computational Mathematics
Applied Mathematics

Access to Document

10.1007/s10589-011-9397-z

Cite this

@article{e141393aedff4b16a61a9577c5b426a5,

title = "A combinatorial optimization algorithm for solving the branchwidth problem",

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.",

keywords = "Branch decomposition, Branchwidth, Implicit enumeration, Partitioning",

author = "Smith, {J. Cole} and Elif Ulusal and Hicks, {Illya V.}",

note = "Funding Information: Acknowledgements The authors are grateful to the comments of two anonymous referees, whose constructive remarks led to an improved version of the paper. We also appreciate the efforts of Dr. Arie Koster, who assisted us in our exact computations of treewidth. Dr. Smith gratefully acknowledges the support of the Air Force Office of Scientific Research under grants FA9550-07-1-0404 and FA9550-08-1-0189. Dr. Hicks gratefully acknowledges the support of the National Science Foundation under grant NSF CMMI-0926618.",

year = "2012",

month = apr,

doi = "10.1007/s10589-011-9397-z",

language = "English (US)",

volume = "51",

pages = "1211--1229",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - A combinatorial optimization algorithm for solving the branchwidth problem

AU - Smith, J. Cole

AU - Ulusal, Elif

AU - Hicks, Illya V.

N1 - Funding Information: Acknowledgements The authors are grateful to the comments of two anonymous referees, whose constructive remarks led to an improved version of the paper. We also appreciate the efforts of Dr. Arie Koster, who assisted us in our exact computations of treewidth. Dr. Smith gratefully acknowledges the support of the Air Force Office of Scientific Research under grants FA9550-07-1-0404 and FA9550-08-1-0189. Dr. Hicks gratefully acknowledges the support of the National Science Foundation under grant NSF CMMI-0926618.

PY - 2012/4

Y1 - 2012/4

N2 - 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.

AB - 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.

KW - Branch decomposition

KW - Branchwidth

KW - Implicit enumeration

KW - Partitioning

UR - http://www.scopus.com/inward/record.url?scp=84862013515&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84862013515&partnerID=8YFLogxK

U2 - 10.1007/s10589-011-9397-z

DO - 10.1007/s10589-011-9397-z

M3 - Article

AN - SCOPUS:84862013515

SN - 0926-6003

VL - 51

SP - 1211

EP - 1229

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 3

ER -

A combinatorial optimization algorithm for solving the branchwidth problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this