Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings

Abstract : Many graph search algorithms use a vertex labeling to compute an ordering of the vertices. We examine such algorithms which compute a peo (perfect elimination ordering) of a chordal graph, and corresponding algorithms which compute an meo (minimal elimination ordering) of a non-chordal graph, an ordering used to compute a minimal triangulation of the input graph. \par We express all known peo-computing search algorithms as instances of a generic algorithm called MLS (Maximal Label Search) and generalize Algorithm MLS into CompMLS, which can compute any peo. \par We then extend these algorithms to versions which compute an meo, and likewise generalize all known meo-computing search algorithms. We show that not all minimal triangulations can be computed by such a graph search, and, more surprisingly, that all these search algorithms compute the same set of minimal triangulations, even though the computed meos are different. \par Finally, we present a complexity analysis of these algorithms.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2009, 23 (1), pp.428-446
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00366108
Contributeur : Genevieve Simonet <>
Soumis le : jeudi 5 mars 2009 - 18:11:47
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 8 juin 2010 - 23:09:44

Fichiers

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

Identifiants

  • HAL Id : lirmm-00366108, version 1

Citation

Anne Berry, Richard Krueger, Geneviève Simonet. Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2009, 23 (1), pp.428-446. 〈lirmm-00366108〉

Partager

Métriques

Consultations de la notice

434

Téléchargements de fichiers

192