Fast algorithms for the maximum clique problem on massive sparse graphs

Bharath Pattabiraman, Md Mostofa Ali Patwary, Assefaw H. Gebremedhin, Wei Keng Liao, Alok Choudhary

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

Abstract

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, information retrieval and many other areas related to the World Wide Web. There exist several algorithms for the problem with acceptable runtimes for certain classes of graphs, but many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques and is able to quickly find maximum cliques in large sparse graphs. Extensive experiments on different kinds of synthetic and real-world graphs show that our new algorithm can be orders of magnitude faster than existing algorithms. We also present a heuristic that runs orders of magnitude faster than the exact algorithm while providing optimal or near-optimal solutions.

Original languageEnglish (US)
Title of host publicationAlgorithms and Models for the Web Graph - 10th International Workshop, WAW 2013, Proceedings
Pages156-169
Number of pages14
DOIs
StatePublished - Dec 1 2013
Event10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013 - Cambridge, MA, United States
Duration: Dec 14 2013Dec 15 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8305 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013
Country/TerritoryUnited States
CityCambridge, MA
Period12/14/1312/15/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Fast algorithms for the maximum clique problem on massive sparse graphs'. Together they form a unique fingerprint.

Cite this