Maximum Cardinality Search for
Computing Minimal Triangulations of Graphs |
| |
| Authors: | Anne Berry Jean R S Blair Pinar Heggernes Barry W Peyton |
| |
| Affiliation: | (1) LIMOS, UMR CNRS 6158, Université Clermont-Ferrand II, F-63177 Aubiere, France;(2) Department of Electrical Engineering and Computer Science, United States Military Academy, West Point, NY 10996, USA;(3) Department of Informatics, University of Bergen, N-5020 Bergen, Norway;(4) Division of Natural Sciences and Mathematics, Dalton State College, Dalton, GA 30720, USA |
| |
| 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. |
| |
| Keywords: | Chordal graphs Minimal triangulations Minimal elimination ordering Minimal fill |
| 本文献已被 SpringerLink 等数据库收录！ |
|
