zbMATH — the first resource for mathematics

Efficient implementation of a minimal triangulation algorithm. (English) Zbl 1019.68809
Möhring, Rolf (ed.) et al., Algorithms - ESA 2002. 10th annual European symposium, Rome, Italy, September 17-21, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2461, 550-561 (2002).
Summary: LB-triang, an algorithm for computing minimal triangulations of graphs, was presented by Berry in 1999, and it gave a new characterization of minimal triangulations. The time complexity was me complexity was conjectured to be \(O(nm)\), but this has remained unproven until our result. In this paper we present and prove an \(O(nm)\) time implementation of LB-triang, and we call the resulting algorithm LB-treedec. The data structure used to achieve this time bound is tree decomposition. We also report from practical runtime tests on randomly generated graphs which indicate that the expected behavior is even better than the proven bound.
For the entire collection see [Zbl 0997.00026].

68W05 Nonnumerical algorithms
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: Link