TY - GEN

T1 - Fast algorithms for the maximum clique problem on massive sparse graphs

AU - Pattabiraman, Bharath

AU - Patwary, Md Mostofa Ali

AU - Gebremedhin, Assefaw H.

AU - Liao, Wei Keng

AU - Choudhary, Alok

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893105331&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893105331&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-03536-9_13

DO - 10.1007/978-3-319-03536-9_13

M3 - Conference contribution

AN - SCOPUS:84893105331

SN - 9783319035352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 156

EP - 169

BT - Algorithms and Models for the Web Graph - 10th International Workshop, WAW 2013, Proceedings

T2 - 10th International Workshop on Algorithms and Models for the Web Graph, WAW 2013

Y2 - 14 December 2013 through 15 December 2013

ER -