The Minimum Degree Heuristic and the Minimal Triangulation Process - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2003

The Minimum Degree Heuristic and the Minimal Triangulation Process

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

Citer

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⟩
170 Consultations
749 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More