Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Genevieve Simonet <>
Submitted on : Thursday, March 5, 2009 - 6:11:47 PM
Last modification on : Wednesday, April 21, 2021 - 8:52:04 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 11:09:44 PM


Files produced by the author(s)


  • HAL Id : lirmm-00366108, version 1


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⟩



Record views


Files downloads