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
ABSTRACT
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.
Go back
Mauricio G.C. Resende's Home PageLast modified: 28 June 2002