Skip to content

Performance comparison of three Bron–Kerbosch algorithm implementations that find all maximal cliques in a graph.

License

Notifications You must be signed in to change notification settings

cornchz/Bron-Kerbosch

Repository files navigation

What is this?

Performance comparison of three Bron–Kerbosch algorithm implementations that find all maximal cliques in a graph.

Implementations

  • Ver1: naive Bron–Kerbosch algorithm
  • Ver2: Ver1 with pivot
  • Ver3: Ver2 with degeneracy ordering

Run

python maximal_cliques.py

Result

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]

Time Comlexity

Worst-case time-complexity analysis is here.

License

BSD License

About

Performance comparison of three Bron–Kerbosch algorithm implementations that find all maximal cliques in a graph.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages