search

darrenstrash / quick-cliques

Quickly compute all maximal cliques of a graph
GNU General Public License v3.0
75 stars 23 forks source link

Question about parallel/distributed solutions for MCE #4

Open viniciusvdias opened 6 years ago

viniciusvdias commented 6 years ago

Hi,

Do you know any parallel/distributed implementations for MCE? It seems to me that the dependency among recursion calls imposes several performance issues in a parallel scenario, for example, in order to maintain the work balanced.

What is your take on that?

Great work by the way.

Cheers,

darrenstrash commented 6 years ago

Hey!

There's been quite a bit of work on parallel enumeration algorithms. The most recent I'm aware of is this paper (which has not yet been published):

Shared-Memory Parallel Maximal Clique Enumeration by Apurba Das, Seyed-Vahid Sanei-Mehri, and Srikanta Tirthapura https://export.arxiv.org/pdf/1807.09417.pdf

They reference some of the earlier works in the area. The upshot is that parallelizing the algorithm by Tomita et al works pretty well, and things can be done to improve it beyond that.

Best, Darren