Maximum cardinality search for computing minimal triangulations. (English) Zbl 1022.68088

Kučera, Luděk (ed.), Graph-theoretic concepts in computer science. 28th international workshop, WG 2002, Český Krumlov, Czech Republic, June 13-15, 2002. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 2573, 1-12 (2002).
Summary: We present a new algorithm, called MCS-M, for computing minimal triangulations of graphs. Lex-BFS, a seminal algorithm for recognizing chordal graphs, was the genesis for two other classical algorithms: Lex-M and MCS. Lex-M extends the fundamental concept used in Lex-BFS, resulting in an algorithm that also computes a minimal triangulation of an arbitrary graph. MCS simplified the fundamental concept used in Lex-BFS, resulting in a simpler algorithm for recognizing chordal graphs. The new simpler algorithm MCS-M combines the extension of Lex-M with the simplification of MCS, achieving all the results of Lex-M in the same time complexity.
For the entire collection see [Zbl 1013.00032].


68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: Link