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
Mauricio G.C. Resende's Home PageLast modified: 11 March 2003