The Library
Combinatorial optimization on graphs of bounded treewidth
Tools
Bodlaender, H. L. and Koster, Arie M. C. A. (2008) Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, Vol.51 (No.3). pp. 255-269. doi:10.1093/comjnl/bxm037 ISSN 0010-4620.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1093/comjnl/bxm037
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Combinatorial optimization, Trees (Graph theory), Graph theory, Algorithms | ||||
Journal or Publication Title: | The Computer Journal | ||||
Publisher: | Oxford University Press | ||||
ISSN: | 0010-4620 | ||||
Official Date: | May 2008 | ||||
Dates: |
|
||||
Volume: | Vol.51 | ||||
Number: | No.3 | ||||
Number of Pages: | 15 | ||||
Page Range: | pp. 255-269 | ||||
DOI: | 10.1093/comjnl/bxm037 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |