Journal
THEORETICAL COMPUTER SCIENCE
Volume 407, Issue 1-3, Pages 564-568Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2008.05.010
Keywords
Maximal cliques; Output sensitive algorithms; Maximal common subgraphs; Enumeration problems
Categories
Funding
- INRIA internship program
Ask authors/readers for more resources
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. (C) 2008 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available