Computing at Glasgow University
Paper ID: 9395
DCS Tech Report Number: TR-2012-334

Distributing an Exact Algorithm for Maximum Clique: maximising the costup
McCreesh,C. Prosser,P.

Publication Type: Tech Report (internal)
Appeared in: SoCS Technical Report Series
Page Numbers : 1-13
Publisher: Dept of Computing Science, University of Glasgow
Year: 2012

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 signi cant speedup in performance with minimal development e ort, i.e. a maximum costup. We present a simple modi cation 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.

PDF Bibtex entry Endnote XML