zbMATH — the first resource for mathematics

Approximating the treewidth of AT-free graphs. (English) Zbl 0988.68124
Brandes, Ulrik (ed.) et al., Graph-theoretic concepts in computer science. 26th international workshop, WG 2000, Konstanz, Germany, June 15-17, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1928, 59-70 (2000).
Summary: Using the specific structure of the minimal separators of AT-free graphs, we give a polynomial time algorithm that computes a triangulation whose width is no more than twice the treewidth of the input graph.
For the entire collection see [Zbl 0952.00042].

68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)