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
- 7384
- Venue
- SIGMOD
- Year
- 2026
- Pagerank
- 4.1905499e-05
- Overall Rank
- 10,074 | 29.99%
- 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 |
| 865 |
Finding the Maximum Clique in Massive Graphs |
2017 |
VLDB |
0.00015775653 |
| 4,085 |
Efficient Maximum k-Plex Computation over Large Sparse Graphs |
2023 |
VLDB |
6.4580586e-05 |
| 4,266 |
Efficient k-Clique Listing: An Edge-Oriented Branching Strategy |
2024 |
SIGMOD |
6.3006582e-05 |
| 4,984 |
Efficient Maximum k-Defective Clique Computation with Improved Time Complexity |
2023 |
SIGMOD |
5.7811667e-05 |
| 5,021 |
Maximal Defective Clique Enumeration |
2023 |
SIGMOD |
5.7481039e-05 |
| 5,148 |
Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach |
2021 |
VLDB |
5.6572863e-05 |
| 5,709 |
Maximum k-Plex Computation: Theory and Practice |
2024 |
SIGMOD |
5.3622436e-05 |
| 6,811 |
Theoretically and Practically Efficient Maximum Defective Clique Search |
2024 |
SIGMOD |
4.9139947e-05 |
| 7,109 |
Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach |
2023 |
SIGMOD |
4.8238188e-05 |
| 7,318 |
Accelerating Maximal Clique Enumeration via Graph Reduction |
2024 |
VLDB |
4.7583643e-05 |
| 9,396 |
Efficient Maximum s-Bundle Search via Local Vertex Connectivity |
2025 |
SIGMOD |
4.3399748e-05 |
| 9,402 |
Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance |
2025 |
VLDB |
4.3399748e-05 |
| 9,404 |
Maximum k-Plex Search: An Alternated Reduction-and-Bound Method |
2025 |
VLDB |
4.3399748e-05 |
| 9,412 |
Efficient k-Clique Count Estimation with Accuracy Guarantee |
2024 |
VLDB |
4.3399748e-05 |
Semantically Similar Papers