Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles SIAM Journal on Discrete Mathematics Year : 2009

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

Dates and versions

lirmm-00366108 , version 1 (05-03-2009)

Identifiers

Cite

Anne Berry, Richard Krueger, Geneviève Simonet. Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings. SIAM Journal on Discrete Mathematics, 2009, 23 (1), pp.428-446. ⟨10.1137/070684355⟩. ⟨lirmm-00366108⟩
383 View
380 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More