×

zbMATH — the first resource for mathematics

Maximum cardinality search for computing minimal triangulations of graphs. (English) Zbl 1090.68080
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 not only recognizes chordality, but also computes a minimal triangulation of an arbitrary graph. MCS simplifies the fundamental concept used in Lex-BFS, resulting in a simpler algorithm for recognizing chordal graphs. The new 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.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Keywords:
chordal graphs
PDF BibTeX Cite
Full Text: DOI