Distributing an Exact Algorithm for Maximum Clique: maximising the costup

Abstract

We take an existing implementation of an algorithm for the maximum clique problem and modify it so that we can distribute it over an ad-hoc cluster of machines. Our goal was to achieve a significant speedup in performance with minimal development effort, i.e. a maximum costup. We present a simple modification to a state-of-the-art exact algorithm for maximum clique that allows us to distribute it across many machines. An empirical study over large hard benchmarks shows that speedups of an order of magnitude are routine for 25 or more machines.

13 pages, 2 Algorithms, 2 figures, 2 tables

References in corpus (1)

• What makes a phase transition? Analysis of the random satisfiability problem

Cited by in corpus (4)

• Replicable Parallel Branch and Bound Search
• Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage
• On the Complexity of Maximum Clique Algorithms: usage of coloring heuristics leads to the 2^(n\5) algorithm running time lower bound
• The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound