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: 5089
Venue: SIGMOD
Year: 2015
Pagerank: 0.00010164289
Overall Rank: 1,633 | 88.80%
DOI: 10.1145/2723372.2746478

Incoming Non-self Citations Over Time

Authors

1. Devora Berlowitz (Hebrew University)
2. Sara Cohen (Hebrew University)
3. Benny Kimelfeld (Technion)

BibTeX Citation

@inproceedings{berlowitz_sigmod15,
        title = {{Efficient Enumeration of Maximal k-Plexes}},
        author = {Berlowitz, Devora and Cohen, Sara and Kimelfeld, Benny},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2746478},
        url = {https://dl.acm.org/doi/10.1145/2723372.2746478},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,453	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD	8.5574945e-05
3,337	Mining Bursting Core in Large Temporal Graphs	2022	VLDB	7.5072753e-05
3,831	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB	7.0862742e-05
5,133	Maximal Defective Clique Enumeration	2023	SIGMOD	6.3533812e-05
5,197	Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach	2021	VLDB	6.3229492e-05
5,374	Hereditary Cohesive Subgraphs Enumeration on Bipartite Graphs: The Power of Pivot-based Approaches	2023	SIGMOD	6.2418958e-05
5,471	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD	6.2061433e-05
5,697	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	6.1174514e-05
8,017	Data Management for Social Networking	2016	PODS	5.5064531e-05
9,551	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB	5.2528121e-05
10,898	Maximum k-Plex Finding: Choices of Pruning Techniques Matter!	2025	VLDB	5.093636e-05
11,173	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD	5.093636e-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
674	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015081844
1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS	0.00010811133
5,103	Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace	2013	PODS	6.3641721e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,551	Maximum k-Plex Search: An Alternated Reduction-and-Bound Method	2025	VLDB
2	11,173	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
3	10,328	Scaling Up k-Clique Percolation Community Detection	2026	SIGMOD
4	5,133	Maximal Defective Clique Enumeration	2023	SIGMOD
5	2,453	Efficient Algorithms for Maximal k-Biplex Enumeration	2022	SIGMOD
6	4,672	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
7	10,332	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD
8	10,365	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD
9	5,471	Maximum k-Plex Computation: Theory and Practice	2024	SIGMOD
10	3,831	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB