A note on the problem of reporting maximal cliques

Reporting the maximal cliques of a graph is a fundamental problem arising in many areas. This note bridges the gap between three papers addressing this problem: the original paper of Bron–Kerbosh [C. Bron, J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Communication of ACM 16 (9) (1973) 575–577], and two papers recently published in TCS, namely that of Tomita et al. [Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science 363 (1) (2006) 28–42], and that of Koch [I. Koch, Fundamental study: Enumerating all connected maximal common subgraphs in two graphs, Theoretical Computer Science 250 (1–2) (2001) 1–30]. In particular, we show that the strategy of Tomita et al. is a simple modification of the Bron–Kerbosch algorithm, based on an (un-exploited) observation raised in Koch’s paper.