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 metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01693126
Contributor : Isabelle Gouat <>
Submitted on : Thursday, January 25, 2018 - 6:14:53 PM
Last modification on : Friday, March 15, 2019 - 1:14:46 AM

File

algorithms-10-00020.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

499

Files downloads

113