On maximum clique problems in very large graphs

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

In External Memory Algorithms, J. Abello and J. Vitter, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, pp. 119-130, American Mathematical Society, 1999


We present an approach for clique and quasi-clique computations in very large multi-digraphs.  We discuss graph decomposition schemes used to break up the problem into several pieces of manageable dimensions. A semi-external greedy randomized adaptive search procedure (GRASP) for finding approximate solutions to the maximum clique problem and maximum quasi-clique problem in very large sparse graphs is presented. We experiment with this heuristic on real data sets collected in the telecommunications industry.  These graphs contain on the order of millions of vertices and edges.

PostScript file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 28 June 2002

Copyright Notice