Massive quasi-clique detection

J. Abello,  M.G.C. Resende, and S. Sudarsky

LATIN 2002: Theoretical Informatics, Lecture Notes in Computer Science,  vol. 2286, pp. 598-612,  2002


We describe techniques that are useful for the detection of dense subgraphs (quasi-cliques) in massive sparse graphs whose vertex set, but not the edge set, fits in RAM. The algorithms rely on efficient semi-external memory algorithms used to preprocess the input and on greedy randomized adaptive search procedures (GRASP) to extract the dense subgraphs. A software platform was put together allowing graphs with hundreds of millions of nodes to be processed. Computational results illustrate the effectiveness of the proposed methods.

PDF file of full paper

DjVu file of full paper

Go back
Mauricio G.C. Resende's Home Page
Last modified: 11 March 2003

Copyright Notice