Fast minimal triangulation algorithm using minimum degree criterion

We propose an algorithm for minimal triangulation which, using simple and efficient strategy, subdivides the input graph in different, almost non-overlapping, subgraphs. Using the technique of matrix multiplication for saturating the minimal separators, we show that the partition of the graph can be computed in time O(nα) where nα is the time required by the binary matrix multiplication. After saturating the minimal separators, the same procedure is recursively applied on each subgraphs. We also present a variant of the algorithm in which the minimum degree criterion is used. In this way, we obtain an algorithm that uses minimum degree criterion and at the same time produces a minimal triangulation, thus shedding new light on the effectiveness of the minimum degree heuristics.