HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070393
Contributor : Frederic Cazals Connect in order to contact the contributor
Submitted on : Tuesday, January 30, 2007 - 5:28:31 PM
Last modification on : Friday, February 4, 2022 - 3:19:34 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 12:29:29 PM

Files

RR-5615.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00070393, version 2

Collections

Citation

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⟩

Share

Metrics

Record views

115

Files downloads

967