Maximum Cardinality Search for Computing Minimal Triangulations of Graphs

Autor:	Pinar Heggernes, Anne Berry, Jean R. S. Blair, Barry W. Peyton
Rok vydání:	2004
Předmět:	Discrete mathematics Hardware_MEMORYSTRUCTURES General Computer Science Applied Mathematics Graph theory Graph Computer Science Applications Combinatorics Chordal graph Theory of computation Software_PROGRAMMINGLANGUAGES Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Algorithmica. 39:287-298
ISSN:	1432-0541 0178-4617
DOI:	10.1007/s00453-004-1084-3
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::94894454590011b794293aa988e979b2 https://doi.org/10.1007/s00453-004-1084-3 Zobrazit plný text záznamu Full text from SpringerLink