Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance
Summary: Tightens exact k-defective clique algorithms by improving the exponential bound from O*(gamma_k^n) to O*(gamma_k^{n-1}) (using gamma_{k-1}<gamma_k) and deriving degeneracy / degeneracy-gap parameterized bounds scaling as (alpha·Delta)^{k+2}·gamma_k^{alpha-1}. Introduces a degree-sequence reduction rule and shows orders-of-magnitude speedups on 290 benchmark graphs. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Lijun Chang
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,074 | Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space | 2026 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 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 |
| 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 |
| 9,406 | Efficient k-Clique Count Estimation with Accuracy Guarantee | 2024 | VLDB | 4.3441378e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,270 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 6.3067205e-05 |
| 4,081 | Efficient Maximum k-Plex Computation over Large Sparse Graphs | 2023 | VLDB | 6.4642761e-05 |
| 6,207 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 5.1572428e-05 |
| 1,650 | Efficient Enumeration of Maximal k-Plexes | 2015 | SIGMOD | 0.00011013428 |
| 847 | Finding the Maximum Clique in Massive Graphs | 2017 | VLDB | 0.00015993322 |
| 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 |
| 5,022 | Maximal Defective Clique Enumeration | 2023 | SIGMOD | 5.7536318e-05 |
| 6,813 | Theoretically and Practically Efficient Maximum Defective Clique Search | 2024 | SIGMOD | 4.9187137e-05 |
| 4,984 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD | 5.7867286e-05 |