Skip to main content
3 of 3
deleted 1 character in body
D.W.
  • 165.6k
  • 21
  • 230
  • 490

What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?

Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from [wikipedia][1]):

BronKerbosch1(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

I have read that the time complexity of some modified versions of this algorithm is $O(3^{n/3})$, but I can't seem to find the running time complexity of the simple version anywhere. [1]: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm "wikipedia"

Juan
  • 41
  • 2