An exact parallel algorithm for the maximum clique problem

P. M. Pardalos, J. Rappe, and M. G. C. Resende

In High Performance Algorithms and Software in Nonlinear Optimization, R. De Leone et al., Eds., Kluwer Academic Publishers, pp. 279-300, 1999

ABSTRACT

In this paper we present a portable exact parallel algorithm for the maximum clique problem on general graphs. Computational results with random graphs and some test graphs from applications are presented. The algorithm is parallelized using the Message Passing Interface (MPI) standard. The algorithm is based on the Carraghan-Pardalos exact algorithm (for unweighted graphs) and incorporates a variant of the greedy randomized adaptive search procedure (GRASP) for maximum independent set of Feo, Resende, and Smith (1994) to obtain good starting solutions.

PostScript file of full paper

PDF file of full paper

Mauricio G.C. Resende's Home Page

Last modified: 28 June 2002

Copyright Notice