A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph

We present a simple unified algorithmic process which uses either LexBFS or MCS on a chordal graph to generate the minimal separators and the maximal cliques in linear time in a single pass.

Data and Resources

Additional Info

Field Value
Source ISSN: 0020-0190
Author Berry, Anne, Pogorelcnik, Romain
Maintainer CCSD
Last Updated May 24, 2026, 22:31 (UTC)
Created May 24, 2026, 22:31 (UTC)
Identifier hal-00678694
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS) ; Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)
creator Berry, Anne
date 2011-06-15T00:00:00
harvest_object_id 04593986-3181-43ef-b118-1346c8e31771
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2023-04-18T00:00:00
relation info:eu-repo/semantics/altIdentifier/doi/10.1016/j.ipl.2011.02.013
set_spec type:ART