Ultimate generalizations of LexBFS and LEX M. (English) Zbl 1171.68589

Kratsch, Dieter (ed.), Graph-theoretic concepts in computer science. 31st international workshop, WG 2005, Metz, France, June 23–25, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-31000-2/pbk). Lecture Notes in Computer Science 3787, 199-213 (2005).
Summary: Many graph search algorithms use a labelling of the vertices 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.
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.
We then extend these algorithms to versions which compute an meo, and likewise generalize all known meo-computing search algorithms. We show the surprising result that all these search algorithms compute the same set of minimal triangulations, even though the computed meos are different.
For the entire collection see [Zbl 1098.68004].


68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
68P10 Searching and sorting
Full Text: DOI