Treewidth Lower Bounds with Brambles |
| |
Authors: | Hans L Bodlaender Alexander Grigoriev Arie M C A Koster |
| |
Affiliation: | 1. Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508, TB, Utrecht, The Netherlands 2. Department of Quantitative Economics, University of Maastricht, P.O. Box 616, 6200, MD, Maastricht, The Netherlands 3. Zuse Institute Berlin (ZIB), Takustra?e 7, 14195, Berlin-Dahlem, Germany
|
| |
Abstract: | In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact
that the treewidth of a graph G is the maximum order of a bramble of G minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is
shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum.
For both algorithms, we report on extensive computational experiments that show that the algorithms often give excellent lower
bounds, in particular when applied to (close to) planar graphs.
This work was partially supported by the Netherlands Organisation for Scientific Research NWO (project Treewidth and Combinatorial Optimisation) and partially by the DFG research group “Algorithms, Structure, Randomness” (Grant number GR 883/9-3, GR 883/9-4). |
| |
Keywords: | Treewidth Lower bound Bramble Planar graph Grid minor Approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|