Three Versions of Clique Search Parallelization
Bogdan Zavalnij

In our paper we present three parallel versions for maximum clique finding algorithms. The parallelization algorithm by quasi coloring was proposed by S. Szabo. In our paper we present the actual implementation of the algorithm and actual results measured on a large scale supercomputer up to 512 cores. We also implemented the proposed tuning of the algorithm and present here the measurements and results. Apart for the implementation we propose another method of tuning the original algorithm, which is based on Las Vegas randomization method. In our paper we compare the measured results of the three versions of the algorithm.

Full Text: PDF