Bron-Kerbosch algorithm for clique finding

Question

Can anyone tell me, where on the web I can find an explanation for Bron-Kerbosch algorithm for clique finding or explain here how it works?

I know it was published in "Algorithm 457: finding all cliques of an undirected graph" book, but I can't find free source that will describe the algorithm.

I don't need a source code for the algorithm, I need an explanation of how it works.

Answer 1

I saw this presentation, however I couldn't understand how the algorithm works from it. It's too simplified. At least for someone like me, who never saw this algorithm before.

I was hoping may be someone have more extensive explanation.

Answer 2

Try finding someone with an ACM student account who can give you a copy of the paper, which is here: http://portal.acm.org/citation.cfm?doid=362342.362367

I just downloaded it, and it's only two pages long, with an implementation in Algol 60!

Answer 3

For what it is worth, I found a Java implementation: http://joelib.cvs.sourceforge.net/joelib/joelib2/src/joelib2/algo/clique/BronKerbosch.java?view=markup

HTH.

Answer 4

There is the algorithm right here I have rewritten it using Java linkedlists as the sets R,P,X and it works like a charm (o good thing is to use the function "retainAll" when doing set operations according to the algorithm).

I suggest you think a little about the implementation because of the optimization issues when rewriting the algorithm

Answer 5

here is python implementation http://kuchaev.com/fun%5Fproblems/?p=17

Answer 6

The python implementation is here Bron-Kerbosh in Python

Answer 7

i find the explanation of the algorithm here: http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf it's a good explanation... but i need a library or implementation in C# -.-'