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 | 5.1725247e-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 |
|---|---|---|---|---|
| 701 | Finding Maximal Cliques in Massive Networks by H*-graph | 2010 | SIGMOD | 0.00014954424 |
| 4,817 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD | 6.5611315e-05 |
| 5,294 | Maximal Defective Clique Enumeration | 2023 | SIGMOD | 6.34833e-05 |
| 9,407 | Efficient k-Clique Count Estimation with Accuracy Guarantee | 2024 | VLDB | 5.3341661e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,938 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 7.0733005e-05 |
| 3,925 | Efficient Maximum k-Plex Computation over Large Sparse Graphs | 2023 | VLDB | 7.0804695e-05 |
| 5,830 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD | 6.132672e-05 |
| 1,627 | Efficient Enumeration of Maximal k-Plexes | 2015 | SIGMOD | 0.0001024273 |
| 1,522 | Finding the Maximum Clique in Massive Graphs | 2017 | VLDB | 0.00010565271 |
| 10,074 | Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space | 2026 | SIGMOD | 5.1725247e-05 |
| 5,657 | Maximum k-Plex Computation: Theory and Practice | 2024 | SIGMOD | 6.1988118e-05 |
| 5,294 | Maximal Defective Clique Enumeration | 2023 | SIGMOD | 6.34833e-05 |
| 6,489 | Theoretically and Practically Efficient Maximum Defective Clique Search | 2024 | SIGMOD | 5.9220971e-05 |
| 4,817 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD | 6.5611315e-05 |