Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Degree-Based Treewidth Lower Bounds
verfasst von : Arie M. C. A. Koster, Thomas Wolle, Hans L. Bodlaender
Erschienen in: Experimental and Efficient Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
N P
-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.