On treewidth approximations

We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a $O(\log k)$ approximation algorithm for the treewidth of arbitrary graphs, where $k$ is the treewidth of the input graph.

Data and Resources

Additional Info

Field Value
Source ISSN: 0166-218X
Author Bouchitté, Vincent, Kratsch, Dieter, Müller, Haiko, Todinca, Ioan
Maintainer CCSD
Last Updated May 10, 2026, 00:16 (UTC)
Created May 10, 2026, 00:16 (UTC)
Identifier hal-00085459
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure de Lyon (ENS de Lyon) ; Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
creator Bouchitté, Vincent
date 2004-05-10T00:00:00
harvest_object_id 314bd1ee-5cc1-4d87-a0e3-76d053c68a38
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-10-13T00:00:00
set_spec type:ART