On treewidth approximations

Vincent Bouchitté (1) , Dieter Kratsch , Haiko Müller , Ioan Todinca (2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans

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.

Mots clés: graph algorithms; treewidth; approximation algoirthms

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

Vincent Bouchitté, Dieter Kratsch, Haiko Müller, Ioan Todinca. On treewidth approximations. Discrete Applied Mathematics, 2004, 136, pp.183-196. ⟨hal-00085459⟩