Combinatorial Optimization on Graphs of Bounded Treewidth

by: Hans L Bodlaender, Arie M Koster

The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 255-269.

View FullText article

DOI, HighWire

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algorithms, graph, parameterized

Abstract

There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given. 10.1093/comjnl/bxm037

@article{citeulike:2746018, abstract = {There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given. 10.1093/comjnl/bxm037}, author = {Bodlaender, Hans L. and Koster, Arie M. }, citeulike-article-id = {2746018}, doi = {10.1093/comjnl/bxm037}, journal = {The Computer Journal}, keywords = {algorithms, graph, parameterized}, month = {May}, number = {3}, pages = {255--269}, posted-at = {2008-05-02 15:42:48}, priority = {1}, title = {Combinatorial Optimization on Graphs of Bounded Treewidth}, url = {http://dx.doi.org/10.1093/comjnl/bxm037}, volume = {51}, year = {2008} }

RIS record

TY - JOUR ID - citeulike:2746018 L3 - citeulike-article-id:2746018 TI - Combinatorial Optimization on Graphs of Bounded Treewidth JF - The Computer Journal VL - 51 IS - 3 SP - 255 EP - 269 N2 - There are many graph problems that can be solved in linear or polynomial time with a dynamic programming algorithm when the input graph has bounded treewidth. For combinatorial optimization problems, this is a useful approach for obtaining fixed-parameter tractable algorithms. Starting from trees and series-parallel graphs, we introduce the concepts of treewidth and tree decompositions, and illustrate the technique with the Weighted Independent Set problem as an example. The paper surveys some of the latest developments, putting an emphasis on applicability, on algorithms that exploit tree decompositions, and on algorithms that determine or approximate treewidth and find tree decompositions with optimal or close to optimal treewidth. Directions for further research and suggestions for further reading are also given. 10.1093/comjnl/bxm037 KW - algorithms KW - graph KW - parameterized AU - Bodlaender, Hans AU - Koster, Arie PY - 2008/05/01/ UR - http://dx.doi.org/10.1093/comjnl/bxm037 ER -

RIS BibTeX