Finding the Maximum Clique in Massive Graphs

Summary: RMC is a randomized solver for maximum clique on massive graphs that uses binary search over clique size with evolving bounds. It builds a seed set S so that finding a w_t-clique in G reduces to a w_t-clique search in S with high probability, enabling efficient, exact maximum clique discovery. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11437
Venue: VLDB
Year: 2017
Pagerank: 0.00015993322
Overall Rank: 847 | 94.11%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
891	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00015564292
3,009	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	7.7214924e-05
4,081	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	6.4642761e-05
4,270	Efficient k-Clique Listing: An Edge-Oriented Branching Strategy	2024	SIGMOD	6.3067205e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
5,149	Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach	2021	VLDB	5.6627295e-05
5,696	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	5.3673968e-05
6,598	One Set to Cover All Maximal Cliques Approximately	2022	SIGMOD	4.9977108e-05
10,074	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	4.1945683e-05
10,530	Most Similar Biclique Search at Scale	2025	VLDB	4.1945683e-05
11,469	Graph Iso/Auto-morphism: A Divide-&-Conquer Approach	2021	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
57	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00065491112
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,598	One Set to Cover All Maximal Cliques Approximately	2022	SIGMOD	4.9977108e-05
891	Maximum Biclique Search at Billion Scale	2020	VLDB	0.00015564292
1,570	KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs	2020	VLDB	0.00011322927
5,022	Maximal Defective Clique Enumeration	2023	SIGMOD	5.7536318e-05
4,984	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	5.7867286e-05
1,650	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD	0.00011013428
6,813	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD	4.9187137e-05
7,320	Accelerating Maximal Clique Enumeration via Graph Reduction	2024	VLDB	4.7629325e-05
10,074	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	4.1945683e-05
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029