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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00366108
Contributor : Genevieve Simonet <>
Submitted on : Thursday, March 5, 2009 - 6:11:47 PM
Last modification on : Monday, January 20, 2020 - 12:12:05 PM
Long-term archiving on: Tuesday, June 8, 2010 - 11:09:44 PM

Files

MLS068435R.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

781

Files downloads

379