Computing a Clique Tree with the Algorithm Maximal Label Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles Algorithms Year : 2017

Computing a Clique Tree with the Algorithm Maximal Label Search

Abstract

The algorithm MLS (Maximal Label Search) is a graph search algorithm that generalizes the algorithms Maximum Cardinality Search (MCS), Lexicographic Breadth-First Search (LexBFS), Lexicographic Depth-First Search (LexDFS) and Maximal Neighborhood Search (MNS). On a chordal graph, MLS computes a PEO (perfect elimination ordering) of the graph. We show how the algorithm MLS can be modified to compute a PMO (perfect moplex ordering), as well as a clique tree and the minimal separators of a chordal graph. We give a necessary and sufficient condition on the labeling structure of MLS for the beginning of a new clique in the clique tree to be detected by a condition on labels. MLS is also used to compute a clique tree of the complement graph, and new cliques in the complement graph can be detected by a condition on labels for any labeling structure. We provide a linear time algorithm computing a PMO and the corresponding generators of the maximal cliques and minimal separators of the complement graph. On a non-chordal graph, the algorithm MLSM, a graph search algorithm computing an MEO and a minimal triangulation of the graph, is used to compute an atom tree of the clique minimal separator decomposition of any graph.
Fichier principal
Vignette du fichier
algorithms-10-00020.pdf (311.43 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

lirmm-01693126 , version 1 (25-01-2018)

Licence

Attribution

Identifiers

Cite

Anne Berry, Geneviève Simonet. Computing a Clique Tree with the Algorithm Maximal Label Search. Algorithms, 2017, 10 (1), pp.#20. ⟨10.3390/a10010020⟩. ⟨lirmm-01693126⟩
347 View
199 Download

Altmetric

Share

Gmail Facebook X LinkedIn More