Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs(arxiv.org)

Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs

http://arxiv.org/abs/1209.5818

4 comments

I've posted a Python version of the main max clique algorithm at https://github.com/peterderivaz/maxclique

This implements the algorithm as I understood it described in the paper.

A small implementation detail that might accelerate things (that I haven't yet implemented) might be to sort the neighbours of each vertex in order of decreasing degree.

This would then allow the calculation of the set in "Pruning 5" of Algorithm 1 to terminate as soon as d(w) <= max.

biscarch14 anni fa

Working on a Clojure implementation here: https://github.com/ChristopherBiscardi/Maximum-Clique--Spars...

Have some other stuff to do, will probably finish later.

[deleted]14 anni fa

Toshio14 anni fa

Implementing this in Haskell is going to make for a very nice weekend project. I'll report back with details of the Github repo if I'm done by the end of the day.

cantankerous14 anni fa

You better. I'm subscribing to that repo.

kxs14 anni fa

I'm interested as well.