The minimum degree heuristic and the minimal triangulation process. (English) Zbl 1255.05186

Bodlaender, Hans L. (ed.), Graph-theoretic concepts in computer science. 29th international workshop, WG 2003, Elspeet, The Netherlands, June 19–21, 2003. Revised papers. Berlin: Springer (ISBN 3-540-20452-0/pbk). Lect. Notes Comput. Sci. 2880, 58-70 (2003).
Summary: The Minimum Degree algorithm, one of the classical algorithms of sparse matrix computations, is a heuristic for computing a minimum triangulation of a graph. It is widely used as a component in every sparse matrix package, and it is known to produce triangulations with few fill edges in practice, although no theoretical bound or guarantee has been shown on its quality. Another interesting behavior of Minimum Degree observed in practice is that it often results in a minimal triangulation. Our goal in this paper is to examine the theoretical reasons behind this good performance. We give new invariants which partially explain the mechanisms underlying this heuristic. We show that Minimum Degree is in fact resilient to error, as even when an undesirable triangulating edge with respect to minimal triangulation is added at some step of the algorithm, at later steps the chances of adding only desirable edges remain intact. We also use our new insight to propose an improvement of this heuristic, which introduces at most as many fill edges as Minimum Degree but is guaranteed to yield a minimal triangulation.
For the entire collection see [Zbl 1029.00043].


05C85 Graph algorithms (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
65F50 Computational methods for sparse matrices


Full Text: DOI