Treewidth: Computational Experiments Export

@misc{koster01treewidth, abstract = {Many NP-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for many optimization problems.}, author = {Koster, A. and Bodlaender, H. and Fouhy, J. and van Hoesel, S.}, citeulike-article-id = {613661}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.2485}, keywords = {complexity, graph\_theory, treewidth}, posted-at = {2006-05-04 17:43:15}, priority = {0}, title = {Treewidth: Computational Experiments}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.2485}, year = {2001} }

TY - GEN ID - koster01treewidth L3 - citeulike-article-id:613661 N2 - Many NP-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for many optimization problems. TI - Treewidth: Computational Experiments KW - complexity KW - graph_theory KW - treewidth AU - Koster, A AU - Bodlaender, H AU - Fouhy, J AU - van Hoesel, S PY - 2001/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.2485 ER -