Reporting maximal cliques: new insights into an old problem

Frédéric Cazals 1 Chinmay Karande 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Reporting maximal cliques of a graph is a fundamental problem arising many areas. Surprisingly, this problem is often tackled resorting to the old Bron-Kerbosch algorithm (1973), or its recent variant by I. Koch (2001). Both algorithms suffer from a poor output sensitivity and worst-cases. In this context, this paper makes three contributions. First, we show that a slight modification of the greedy pivoting strategy used by I. Koch allows one to get rid of worst-cases, also improving overall performances. Second, exploiting the recursive structure of non maximal cliques, we show the pivoting strategy developed by I. Koch is a particular case of a more general optimization strategy based on the concept of {\em dominated} nodes. Using different instantiations of this concept, we design four modified Bron-Kerbosch algorithms, with better output-sensitivity. Third, we discuss implementation issues and provide a detailed experimental study on random graphs. The bottom-line of this study is the investigation of the trade-off between output sensitivity and the overhead associated to the identification of dominated nodes.
Type de document :
[Research Report] RR-5615, INRIA. 2006, pp.25
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
Contributeur : Frederic Cazals <>
Soumis le : mardi 30 janvier 2007 - 17:28:31
Dernière modification le : samedi 27 janvier 2018 - 01:31:03
Document(s) archivé(s) le : mardi 21 septembre 2010 - 12:29:29


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00070393, version 2



Frédéric Cazals, Chinmay Karande. Reporting maximal cliques: new insights into an old problem. [Research Report] RR-5615, INRIA. 2006, pp.25. 〈inria-00070393v2〉



Consultations de la notice


Téléchargements de fichiers