Research map / Learning theory and algorithms / Combinatorial and search optimization
NukCP: An Improved Local Search Algorithm for Maximum k-Club Problem
Jiejiang Chen, Yiyuan Wang, Shaowei Cai, Minghao Yin, Yupeng Zhou, Jieyu Wu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NukCP instead of the strongest reported baseline | Maximum k-club search · Random graphs, n300d0.015, k=4 | maximum club size (family average): 61.4 -> 62.7 | Improved |
| Use NukCP instead of VNS | Maximum k-club search · DIMACS football, k=3 | maximum club size: 56 -> 58 | Improved |
| Use NukCP instead of VNS | Maximum k-club search · DIMACS email, k=3 | maximum club size: 215 -> 212 | Hurt |
| Use NukCP instead of the strongest reported baseline | Maximum k-club search · Massive graphs, ca-coauthors-dblp, k=3 | maximum club size: 4369 -> 7098 | Improved |
| Use NukCP instead of the strongest reported baseline | Maximum k-club search · Massive graphs, soc-livejournal, k=3 | maximum club size: 3683 -> 3517 | Hurt |
| Use DRM instead of TRIM for initial graph reduction | NukCP · Massive graphs | reduction runtime (seconds): 844.92 -> 376.43 | Improved |
| Use DRM instead of TRIM for initial graph reduction | NukCP · Massive graphs | reduction ratio: 57.72% -> 58.77% | Improved |
| Replace STCC with DCC (ablation) | NukCP · All benchmarks | instances with better results than the variant: 1 better, 1 worse (random graphs); 1 better, 0 worse (DIMACS); 15 better, 4 worse (massive graphs) | Mixed |
| Replace STCC with BoundedCC (ablation) | NukCP · All benchmarks | instances with better results than the variant: 1 better, 1 worse (random graphs); 1 better, 0 worse (DIMACS); 18 better, 3 worse (massive graphs) | Mixed |
| Use NukCP instead of VNS | Maximum k-club search · Massive graphs, k=2 | average runtime (seconds): 1288.89 -> 33.82 | Improved |
| Increase k to larger values | NukCP · Massive graphs | average runtime (seconds): 33.82; 912.61; 2071.4 | Hurt |
Closest papers by meaning
- Two Efficient Local Search Algorithms for Maximum Weight Clique Problem (AAAI 2016 · similarity 0.90)
- KD-Club: An Efficient Exact Algorithm with New Coloring-Based Upper Bound for the Maximum k-Defective Clique Problem (AAAI 2024 · similarity 0.89)
- A Fast Exact Solver with Theoretical Analysis for the Maximum Edge-Weighted Clique Problem (AAAI 2024 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.84)
- An Elite-guided Weighted Simulated Annealing Algorithm for the Clique Partitioning Problem (AAAI 2025 · similarity 0.84)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
