Treewidth computations II. Lower bounds |
| |
Authors: | Hans L Bodlaender Arie MCA Koster |
| |
Affiliation: | a Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands b Lehrstuhl II für Mathematik, RWTH Aachen University, Wüllnerstr. 5b, D-52062 Aachen, Germany |
| |
Abstract: | For several applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs. |
| |
Keywords: | Treewidth Lower bounds Heuristics Graph algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|