4 ms·

Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs

• Toshio 14y 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 14y ago
    You better. I'm subscribing to that repo.
    • kxs 14y ago
      I'm interested as well.
• deleted 14y ago
  [deleted]
• peterderivaz 14y ago
  I've posted a Python version of the main max clique algorithm at https://github.com/peterderivaz/maxclique 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 14y ago
  Working on a Clojure implementation here: https://github.com/ChristopherBiscardi/Maximum-Clique--Sparse-Graphs- https://github.com/ChristopherBiscardi/Maximum-Clique--Spars... Have some other stuff to do, will probably finish later.