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.
Type de document :
Article dans une revue
Algorithms, MDPI, 2017, 10 (1), pp.#20. 〈10.3390/a10010020〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01693126
Contributeur : Isabelle Gouat <>
Soumis le : jeudi 25 janvier 2018 - 18:14:53
Dernière modification le : vendredi 15 mars 2019 - 01:14:46

Fichier

algorithms-10-00020.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

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〉

Partager

Métriques

Consultations de la notice

381

Téléchargements de fichiers

68