Inproceedings,
On Maximum Clique Problems In Very Large Graphs
In External Memory Algorithms, 50, page 119--130. (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 semiexternal greedy randomized adaptive search procedure (GRASP) for finding approximate solutions to the maximum clique problem and maximum quasiclique 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. 1. Introduction The proliferation of massive data sets brings with it a series of special computational challenges. Many of these data sets can be modeled as very large multidigraphs M with a special set of edge attributes that represent special characteristics of the application at hand 1. Understanding the structure of the underlying digraph D(M) is essential for storage organization and information retrieval...
