Performance comparison of three Bron–Kerbosch algorithm implementations that find all maximal cliques in a graph.
- Ver1: naive Bron–Kerbosch algorithm
- Ver2: Ver1 with pivot
- Ver3: Ver2 with degeneracy ordering
python maximal_cliques.py
Stdout result for the sample data
## Naive Bron–Kerbosch algorithm
26 recursive calls
0: [1, 2, 3, 4]
1: [2, 3, 5]
2: [5, 6, 7]
## Bron–Kerbosch algorithm with pivot
14 recursive calls
0: [1, 2, 3, 4]
1: [5, 2, 3]
2: [5, 6, 7]
## Bron–Kerbosch algorithm with pivot and degeneracy ordering
19 recursive calls
0: [6, 5, 7]
1: [5, 2, 3]
2: [1, 2, 3, 4]
Worst-case time-complexity analysis is here.