Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Thursday, January 25, 2018 - 6:14:53 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM


Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution 4.0 International License



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



Record views


Files downloads