The DIGRAPHS_BronKerbosch implementation of the Bron–Kerbosch algorithm, which @wilfwilson wrote 10 years ago, is happily doing its job in cliques.gi. But it has several TODOs that hint at ways it could be improved.
A nice task for a VIP or dissertation might be to have another look at:
- pivot strategies (several commented out and moved around);
- use of
DigraphDegeneracyOrdering which is described on Wikipedia but which we don't do;
- anything else that occurs to a careful reader.
Playing around with these different variations and doing some benchmarks could be a nice project, and could guide improvements. Any benchmarks should cover the use of all the different arguments, and different kinds of automorphism group that the graph might have.
The
DIGRAPHS_BronKerboschimplementation of the Bron–Kerbosch algorithm, which @wilfwilson wrote 10 years ago, is happily doing its job in cliques.gi. But it has several TODOs that hint at ways it could be improved.A nice task for a VIP or dissertation might be to have another look at:
DigraphDegeneracyOrderingwhich is described on Wikipedia but which we don't do;Playing around with these different variations and doing some benchmarks could be a nice project, and could guide improvements. Any benchmarks should cover the use of all the different arguments, and different kinds of automorphism group that the graph might have.