A wide-range algorithm for minimal triangulation from an arbitrary ordering

We present a new algorithm, called LB-Triang, which computes minimal triangulations. We give both a straightforward 0 (nm') time implementation and a more involved 0 (nm) time implementation, thus matching the best known algorithms for this problem. Our algorithm is based on a process by Lekkerkerker and Boland for recognizing chordal graphs which checks in an arbitrary order whether the minimal separators contained in each vertex neighborhood are cliques. LB-Triang checks each vertex for this property and adds edges whenever necessary to make each vertex obey this property. As the vertices can be processed in any order, LB-Triang is able to compute any minimal triangulation of a given graph, which makes it significantly different from other existing triangulation techniques. We examine several interesting and useful properties of this algorithm, and give some experimental results. (C) 2004 Elsevier Inc. All rights reserved.