The Minimum Degree Heuristic and the Minimal Triangulation Process - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2003

The Minimum Degree Heuristic and the Minimal Triangulation Process


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.
Fichier principal
Vignette du fichier
D147.PDF (243.39 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00191916 , version 1 (26-11-2007)



Anne Berry, Pinar Heggernes, Geneviève Simonet. The Minimum Degree Heuristic and the Minimal Triangulation Process. WG 2003 - 29th International Workshop on Graph-Theoretic Concepts in Computer Science, May 2003, Elspeet, Netherlands. pp.58-70, ⟨10.1007/978-3-540-39890-5_6⟩. ⟨lirmm-00191916⟩
171 View
764 Download



Gmail Mastodon Facebook X LinkedIn More