%0 Journal Article %1 bodlaender_07_optimization-bounded-treewidth %A Bodlaender, Hans L. %A Koster, Arie M. C. A. %D 2007 %J The Computer Journal %K combinatorial bounded treewidth optimization %P bxm037 %R 10.1093/comjnl/bxm037 %T Combinatorial Optimization on Graphs of Bounded Treewidth %U http://comjnl.oxfordjournals.org/cgi/content/abstract/bxm037v1 %X 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.

@article{bodlaender_07_optimization-bounded-treewidth, 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.}, added-at = {2010-05-24T23:08:05.000+0200}, author = {Bodlaender, Hans L. and Koster, Arie M. C. A.}, biburl = {https://www.bibsonomy.org/bibtex/28edf1a8b04be609e7fbdf7c3fec1c51b/ukoethe}, description = {Combinatorial Optimization on Graphs of Bounded Treewidth -- Bodlaender and Koster, 10.1093/comjnl/bxm037 -- The Computer Journal}, doi = {10.1093/comjnl/bxm037}, eprint = {http://comjnl.oxfordjournals.org/cgi/reprint/bxm037v1.pdf}, file = {bodlaender_07_optimization-bounded-treewidth.pdf:bodlaender_07_optimization-bounded-treewidth.pdf:PDF}, interhash = {372628ddd8572b9f672126ba7acfba71}, intrahash = {8edf1a8b04be609e7fbdf7c3fec1c51b}, journal = {The Computer Journal}, keywords = {combinatorial bounded treewidth optimization}, pages = {bxm037}, timestamp = {2010-05-24T23:08:05.000+0200}, title = {Combinatorial Optimization on Graphs of Bounded Treewidth}, url = {http://comjnl.oxfordjournals.org/cgi/content/abstract/bxm037v1}, year = 2007 }