| Konrad-Zuse-Zentrum fu¨r Informationstechnik Berlin (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgraph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds. 1 | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||