Back to papers
Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space
Summary: Clique-first branch-and-bound with a new pivoting yields worst-case optimal search space O(3^{n/3}·n^k) for maximal k-defective clique enumeration (Ω lower bound for constant k). Uses diameter-two to get O(n·3^{δ/3}(δΔ)^k), extends to max-k search with up to 10^4× speedups.
(summarized by gpt-5-mini on Feb 11 2026)
- Paper ID
- 7383
- Venue
- SIGMOD
- Year
- 2026
- Pagerank
- 4.1945683e-05
- Overall Rank
- 10,074 | 29.92%
- DOI
-
10.1145/3769787
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank |
Citing Paper |
Year |
Venue |
Pagerank |
Outgoing Citations (Sorted by Pagerank)
Showing 14 of 14 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank |
Cited Paper |
Year |
Venue |
Pagerank |
| 847 |
Finding the Maximum Clique in Massive Graphs |
2017 |
VLDB |
0.00015993322 |
| 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,984 |
Efficient Maximum k-Defective Clique Computation with Improved Time Complexity |
2023 |
SIGMOD |
5.7867286e-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,813 |
Theoretically and Practically Efficient Maximum Defective Clique Search |
2024 |
SIGMOD |
4.9187137e-05 |
| 7,111 |
Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach |
2023 |
SIGMOD |
4.8284522e-05 |
| 7,320 |
Accelerating Maximal Clique Enumeration via Graph Reduction |
2024 |
VLDB |
4.7629325e-05 |
| 9,390 |
Efficient Maximum s-Bundle Search via Local Vertex Connectivity |
2025 |
SIGMOD |
4.3441378e-05 |
| 9,396 |
Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance |
2025 |
VLDB |
4.3441378e-05 |
| 9,398 |
Maximum k-Plex Search: An Alternated Reduction-and-Bound Method |
2025 |
VLDB |
4.3441378e-05 |
| 9,406 |
Efficient k-Clique Count Estimation with Accuracy Guarantee |
2024 |
VLDB |
4.3441378e-05 |
Semantically Similar Papers