Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Berry, A., Blair, J., Heggernes, P. et al. Maximum Cardinality Search for Computing Minimal Triangulations of Graphs. Algorithmica 39, 287–298 (2004). https://doi.org/10.1007/s00453-004-1084-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-004-1084-3