Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs

by adulau • 14 years ago

74 5 14 years ago

Toshio• 14 years ago

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.

cantankerous• 14 years ago

You better. I'm subscribing to that repo.

kxs• 14 years ago

I'm interested as well.

peterderivaz• 14 years ago

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.

biscarch• 14 years ago

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

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

Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs

Related Stories