Approximating the treewidth of AT-free graphs

Using the specific structure of AT-free graphs, we give a 2-approximation algorithm for their treewidth.

Data and Resources

Additional Info

Field Value
Source ISSN: 0166-218X
Author Bouchitté, Vincent, Todinca, Ioan
Maintainer CCSD
Last Updated May 10, 2026, 00:07 (UTC)
Created May 10, 2026, 00:07 (UTC)
Identifier hal-00085474
Language en
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 2003-05-10T00:00:00
harvest_object_id eedf12ad-68a5-47a3-83d8-a7853b40cdbe
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