Efficient Enumeration of Maximal k-Plexes

Summary: First provably efficient algorithms for enumerating maximal k-plexes and maximal connected k-plexes. Polynomial delay for constant k and incremental FPT delay in k, with real and synthetic experiments showing scalability and superiority over prior work. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5027
Venue: SIGMOD
Year: 2015
Pagerank: 0.00011013428
Overall Rank: 1,650 | 88.53%
DOI: 10.1145/2723372.2746478

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,521	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6065919e-05
4,081	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	6.4642761e-05
4,208	Mining Bursting Core in Large Temporal Graphs	2022	VLDB	6.357214e-05
5,022	Maximal Defective Clique Enumeration	2023	SIGMOD	5.7536318e-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,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05
6,532	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	5.0245678e-05
7,998	Data Management for Social Networking	2016	PODS	4.6101889e-05
9,398	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	4.3441378e-05
10,646	Maximum k-Plex Finding: Choices of Pruning Techniques Matter!	2025	VLDB	4.1945683e-05
10,959	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	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
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
1,073	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00014264992
4,653	Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace	2013	PODS	6.0227856e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,398	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	4.3441378e-05
10,959	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	4.1945683e-05
10,033	Scaling Up k-Clique Percolation Community Detection	2026	SIGMOD	4.1945683e-05
5,022	Maximal Defective Clique Enumeration	2023	SIGMOD	5.7536318e-05
2,521	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.6065919e-05
4,984	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD	5.7867286e-05
10,037	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.1945683e-05
10,074	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	4.1945683e-05
5,696	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	5.3673968e-05
4,081	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	6.4642761e-05