Approximating the treewidth of AT-free graphs

Article Dans Une Revue Discrete Applied Mathematics Année : 2003

(1) , (2)

1
2

Vincent Bouchitté

Laboratoire de l'Informatique du Parallélisme

Ioan Todinca

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

treewidth AT-free graphs

Algorithme et structure de données [cs.DS]

https://hal.science/hal-00085474

Soumis le : mercredi 12 juillet 2006-15:43:22

Dernière modification le : jeudi 11 mai 2023-11:56:10

hal-00085474 , version 1 (12-07-2006)

Vincent Bouchitté, Ioan Todinca. Approximating the treewidth of AT-free graphs. Discrete Applied Mathematics, 2003, 131, pp.11-37. ⟨hal-00085474⟩

ENS-LYON CNRS INRIA UNIV-LYON1 UNIV-ORLEANS MSL MSL-THESE UDL

61 Consultations

0 Téléchargements