In High Performance Algorithms and Software in Nonlinear Optimization, R. De Leone et al., Eds., Kluwer Academic Publishers, pp. 279-300, 1999
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 PageLast modified: 28 June 2002