Sequential and Parallel Triangulating Algorithms for Elimination Game and New Insights on Minimum Degree

Abstract : Elimination Game is a well known algorithm that simulates Gaussian elimination of matrices on graphs, and it computes a triangulation of the input graph. The number of fill edges in the computed triangulation is highly dependent on the order in which Elimination Game processes the vertices, and in general the produced triangulations are neither minimum nor minimal. In order to obtain a triangulation which is close to minimum, the Minimum Degree heuristic is widely used in practice, but until now little was known on the theoretical mechanisms involved. In this paper we show some interesting properties of Elimination Game; in particular that it is able to compute a partial minimal triangulation of the input graph regardless of the order in which the vertices are processed. This results in a new algorithm to compute minimal triangulations that are sandwiched between the input graph and the triangulation resulting from Elimination Game. One of the strengths of the new approach is that is is easily parallelizable, and thus we are able to present the first parallel algorithm to compute such sandwiched minimal triangulations. In addition, the insight that we gain through Elimination Game is used to partly explain the good behavior of the Minimum Degree algorithm. We also give a new algorithm for producing minimal triangulations that is able to use the minimum degree idea to a wider extent.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2008, 409 (3), pp.601-616
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00366031
Contributeur : Genevieve Simonet <>
Soumis le : jeudi 5 mars 2009 - 15:09:14
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 12:56:09

Fichier

GPAJUN08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00366031, version 1

Citation

Anne Berry, Elias Dahlhaus, Pinar Heggernes, Geneviève Simonet. Sequential and Parallel Triangulating Algorithms for Elimination Game and New Insights on Minimum Degree. Theoretical Computer Science, Elsevier, 2008, 409 (3), pp.601-616. 〈lirmm-00366031〉

Partager

Métriques

Consultations de la notice

437

Téléchargements de fichiers

697