Please wait a minute...
Shopping Cart Email List Chinese
Advanced Search Fig/Tab
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Featured Articles  |  Most Downloaded  |  Most Reading
Online Submission Subscribe to Our RSS Content Feed
Front. Comput. Sci.    2025, Vol. 19 Issue (6) : 196403    https://doi.org/10.1007/s11704-024-40238-8
Theoretical Computer Science
Improving local search algorithms for clique relaxation problems via group driven initialization
Rui SUN1,2, Yiyuan WANG1,2(), Minghao YIN1,2()
1. School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
2. Key Laboratory of Applied Statistics of Ministry of Education, Northeast Normal University, Changchun 130117, China
 Download: PDF(5790 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Clique relaxation problems are important extension versions of the maximum clique problem with extensive real-world applications. Although lots of studies focus on designing local search algorithms for solving these problems, almost all state-of-the-art local search algorithms adopt a common general initialization method. This paper develops a general group driven initialization method for clique relaxation problems. The proposed method uses two kinds of ways to divide vertices into some subgroups by using the useful information of the search procedure and the structure information of a given instance and then constructs a good initial solution by considering the generated group information. We apply the proposed initialization method to two clique relaxation problems. Experimental results demonstrate that the proposed initialization method clearly improves the performance of state-of-the-art algorithms for the clique relaxation problems.
Keywords combinatorial optimization      clique relaxation problems      group driven initialization      local search      group information     
Corresponding Author(s): Yiyuan WANG,Minghao YIN   
Just Accepted Date: 04 June 2024   Issue Date: 19 July 2024
 Cite this article:   
Rui SUN,Yiyuan WANG,Minghao YIN. Improving local search algorithms for clique relaxation problems via group driven initialization[J]. Front. Comput. Sci., 2025, 19(6): 196403.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-024-40238-8
https://academic.hep.com.cn/fcs/EN/Y2025/V19/I6/196403
  
  
Fig.1  An example for local optimal matrix M. Updating M by using Dlbest={v1,v4,v5}. The red numbers are the updated elements in M.
  
  
  
  
  
Instances k NuQClq NuQClq-GDI Instances k NuQClq NuQClq-GDI Instances k NuQClq NuQClq-GDI
max avg max avg max avg max avg max avg max avg
C4000.5 0.8 53 52.9 53 52.7 frb40-19-5 0.999 40 39.7 40 40 frb56-25-5 0.999 57 55.7 57 56
brock400_1 0.999 27 26 27 25.6 frb50-23-4 0.999 51 50.9 51 51 frb59-26-1 0.999 59 58.3 59 58.5
brock800_2 0.999 24 24 24 23.7 frb53-24-1 0.999 53 52.9 54 53.1 frb59-26-4 0.999 59 58.1 60 58.4
brock800_3 0.999 22 22 25 22.3 frb53-24-2 0.999 54 53 54 53.1 frb59-26-5 0.999 60 58.7 60 59
C1000.9 0.999 70 69.9 70 70 frb53-24-5 0.999 54 52.8 54 52.6 hamming10-4 0.95 88 87.3 88 87.1
C2000.9 0.999 82 79.5 80 79.5 frb56-25-1 0.999 56 55.5 57 55.6 san400_0.7_2 0.95 65 64 65 65
C4000.5 0.9 30 30 31 30.2 frb56-25-2 0.999 56 55.3 57 55.5 san400_0.7_3 0.95 40 39.6 40 39.9
frb100-40 0.999 99 98.6 101 98.7 frb56-25-4 0.999 57 55.4 57 55.7
Tab.1  Experimental results of NuQClq and NuQClq-GDI on classic instances
Instances k NuQClq NuQClq-GDI Instances k NuQClq NuQClq-GDI Instances k NuQClq NuQClq-GDI
max avg max avg max avg max avg max avg max avg
LiveJournal 0.9 430 427.2 430 424.4 rgg-n_2_24_s0 0.9 28 25.5 28 25.4 web-wikipedia_link 0.9 452 250 660 357.9
0.8 472 471 472 472 0.8 31 29.6 34 30.6 0.8 903 312.4 945 511.4
0.6 628 619.8 628 628 0.7 38 35.2 38 35.4 0.7 1214 562.1 1156 512
orkut 0.9 124 116.9 115 109.7 0.6 46 42.9 44 41.8 0.6 597 431.4 1156 755.5
0.8 166 146.3 166 149.1 soc-orkut 0.9 107 93.4 114 101.9 web-wikipedia-growth 0.9 47 36.7 49 33.2
0.7 201 194.9 202 201.1 0.8 159 129 159 135.9 0.8 70 59.2 75 61.9
web-Google 0.8 69 68.9 69 69 0.7 194 170.7 194 171.1 wikipedia_link_en 0.9 74 50.5 74 58.7
wiki-topcats 0.9 47 38.4 47 41.3 0.6 244 225.2 244 228.6 0.8 60 42.2 111 54.6
0.8 68 54.5 68 60.3 soc-sinaweibo 0.9 112 105.2 112 106.3 0.7 150 69.7 150 92.8
0.7 102 83.1 102 84.5 0.8 183 122.2 183 122.5 soc-ljournal-2008 0.9 475 435.7 475 460.8
0.6 171 143 171 133.2 0.7 263 217.4 263 188.7 0.8 542 514.7 542 542
dbpedia-link 0.9 57 49.5 57 48.5 0.6 241 201 345 218 0.7 655 638.7 655 655
0.8 87 67.6 87 76.8 twitter_mpi 0.8 312 312 501 387.6 0.6 793 775.2 793 776.1
0.7 149 89.2 149 103.2 web-baidu-baike 0.9 24 24 28 24.4 soc-twitter-higgs 0.6 257 251 257 255.9
0.6 220 127.8 220 141.3 0.8 33 33 34 33.1
Tab.2  Experimental results of NuQClq and NuQClq-GDI on sparse instances
AlgorithmBenchmark#instmaxavg
#better#worse#better#worse
FD-TS-GDI vs.classic instances363345398
FD-TSsparse instances30331117
DCCplex-GDI vs.classic instances363201783
DCCplexsparse instances30310106
Tab.3  Comparative results on all the MKPP benchmarks
Instances k FD-TS FD-TS-GDI Instances k FD-TS FD-TS-GDI Instances k FD-TS FD-TS-GDI
max avg max avg max avg max avg max avg max avg
brock400_4 2 33 32.2 33 33 san400_0.7_3 2 27 26.7 27 27 gen400_p0.9_65 3 101 100.7 101 101
C1000.9 2 82 81.2 82 82 san400_0.9_1 2 102 101.5 102 102 keller6 3 91 90.3 90 89.5
C2000.5 2 20 19.5 20 19.3 brock800_1 3 30 29.7 30 29.5 san400_0.7_2 3 47 46.1 47 47
C2000.9 2 91 90.2 91 90.6 brock800_2 3 30 30 30 29.8 brock800_2 4 34 33.6 34 33.4
C4000.5 2 21 20.2 21 20.1 brock800_3 3 30 29.9 30 30 brock800_3 4 34 33.8 34 34
frb100-40 2 124 123.1 124 123.2 C1000.9 3 95 94.5 95 95 C1000.9 4 108 107.2 109 107.7
frb50-23-1 2 67 65.9 67 66.2 C2000.5 3 23 22.1 22 22 C2000.9 4 119 118.1 120 118.5
frb50-23-2 2 66 65.5 66 66 C2000.9 3 106 104.5 105 104.6 DSJC1000.5 4 24 23.8 24 23.9
frb50-23-3 2 64 63.9 65 63.8 frb100-40 3 148 146.8 147 145.9 frb100-40 4 168 167.9 168 167.1
frb50-23-4 2 66 65.3 66 65.4 frb50-23-1 3 79 78 79 78.1 frb50-23-1 4 91 89.8 92 90.7
frb50-23-5 2 66 65.7 66 66 frb50-23-2 3 78 77.9 79 78.4 frb50-23-2 4 91 89.7 91 90
frb53-24-1 2 70 69.2 71 70.4 frb50-23-3 3 76 75 76 75.3 frb50-23-3 4 87 86.3 87 86.2
frb53-24-2 2 70 68.7 70 69.2 frb50-23-4 3 78 77.2 78 78 frb50-23-4 4 90 89.2 90 89.8
frb53-24-3 2 69 68.7 70 69.2 frb50-23-5 3 78 77.9 79 78 frb50-23-5 4 90 89.7 91 90.2
frb53-24-4 2 69 68.5 70 68.8 frb53-24-1 3 83 83 84 83.4 frb53-24-1 4 97 96.3 98 96.7
frb53-24-5 2 68 67.1 68 67.3 frb53-24-2 3 82 81.1 82 81.5 frb53-24-3 4 95 94.2 96 94.7
frb56-25-1 2 74 73.2 74 73.9 frb53-24-3 3 82 81.5 83 82.1 frb53-24-4 4 95 93.8 96 94.4
frb56-25-2 2 74 73.1 75 73.9 frb53-24-4 3 82 81.3 83 82 frb53-24-5 4 92 91.8 93 92.3
frb56-25-3 2 73 72.1 73 72.5 frb53-24-5 3 80 79.6 82 80.2 frb56-25-1 4 101 100.8 103 101.7
frb56-25-4 2 73 72.2 73 72.1 frb56-25-1 3 88 87.2 89 88 frb56-25-2 4 100 99.9 101 100.3
frb56-25-5 2 72 72 73 72.1 frb56-25-2 3 88 86.6 88 87.5 frb56-25-3 4 99 98.1 99 98.5
frb59-26-1 2 77 76.7 78 77.3 frb56-25-3 3 86 85.3 87 85.8 frb56-25-4 4 98 97.6 99 98.1
frb59-26-2 2 78 76.9 78 77.1 frb56-25-4 3 87 85.4 86 85.2 frb56-25-5 4 99 98.2 99 98.4
frb59-26-3 2 76 75.5 77 75.9 frb56-25-5 3 86 85.2 86 85.5 frb59-26-1 4 105 104.6 108 105.5
frb59-26-4 2 77 75.9 77 76.5 frb59-26-1 3 91 90.8 92 91.3 frb59-26-2 4 105 104.4 105 104.7
frb59-26-5 2 76 75.7 77 76.4 frb59-26-2 3 91 90.7 92 91.2 frb59-26-4 4 105 103.5 105 103.8
gen400_p0.9_65 2 73 72 74 73.1 frb59-26-3 3 91 90.2 91 90.6 frb59-26-5 4 105 103.3 105 103.8
gen400_p0.9_75 2 79 78.2 79 79 frb59-26-4 3 91 90 91 90.3 keller6 4 106 104.4 113 107.9
MANN_a81 2 2162 2161.7 2162 2161.8 frb59-26-5 3 90 89.3 91 90
Tab.4  Experimental results of FD-TS and FD-TS-GDI on classic instances
Instances k FD-TS FD-TS-GDI Instances k FD-TS FD-TS-GDI Instances k FD-TS FD-TS-GDI
max avg max avg max avg max avg max avg max avg
bn-human-BNU*_1-bg 2 214 210.2 214 208.8 soc-orkut-dir 3 65 63.5 65 64 soc-orkut 4 62 62 62 61.8
dbpedia-link 2 36 35.6 36 35.3 twitter_mpi 3 173 160.4 173 173 soc-orkut-dir 4 70 67.5 71 68.4
soc-orkut 2 52 51.2 52 51.5 web-baidu-baike 3 33 27.8 25 22.7 soc-sinaweibo 4 62 56.4 62 62
soc-orkut-dir 2 58 57.1 58 57.8 web-wikipedia-growth 3 33 31.2 33 31.1 web-baidu-baike 4 33 25.2 33 23.9
web-baidu-baike 2 33 24.5 33 24 wikipedia_link_en 3 48 19.5 48 21 web-wikipedia-growth 4 34 33.7 35 32.7
wikipedia_link_en 2 46 27.9 46 32.7 bn-human-BNU*_1-bg 4 236 235 236 235.4 wikipedia_link_en 4 48 24.3 50 22.7
bn-human-BNU*_1-bg 3 226 224.3 226 224.7 bn-human-BNU*_2-bg 4 204 200.6 204 202.3
soc-orkut 3 59 57 59 58.2 dbpedia-link 4 40 39.6 40 39
Tab.5  Experimental results of FD-TS and FD-TS-GDI on sparse instances
Instances k DCCplex DCCplex-GDI Instances k DCCplex DCCplex-GDI Instances k DCCplex DCCplex-GDI
max avg max avg max avg max avg max avg max avg
brock400_4 2 33 32.8 33 32.6 C1000.9 3 95 95 96 95.2 brock800_3 4 34 33.9 34 34
brock800_4 2 26 25.4 26 25.8 C2000.5 3 23 22.1 23 22.3 C1000.9 4 109 107.9 109 108.1
C1000.9 2 82 81.8 82 82 C2000.9 3 108 107.3 109 107.9 C2000.9 4 122 121.2 122 121.3
C2000.5 2 20 19.6 20 19.8 C4000.5 3 24 23.6 24 23.9 C4000.5 4 26 26 27 26.6
C2000.9 2 93 92.2 94 92.7 frb100-40 3 156 153.9 156 154.4 DSJC1000.5 4 24 23.8 24 24
C4000.5 2 21 20.6 21 20.8 frb50-23-1 3 79 78.7 79 79 frb100-40 4 178 176.3 179 176.9
frb100-40 2 128 127.5 129 128.2 frb50-23-2 3 79 78.8 79 79 frb50-23-1 4 92 91.4 92 91.5
frb50-23-1 2 66 66 67 66.1 frb50-23-3 3 76 75.8 76 76 frb50-23-2 4 91 90.7 91 90.9
frb50-23-5 2 66 66 67 66.4 frb50-23-4 3 79 78.8 79 78.9 frb50-23-3 4 88 87.1 88 87.2
frb53-24-1 2 71 70.9 71 70.8 frb50-23-5 3 79 78.7 80 79.2 frb50-23-4 4 91 90.7 91 90.9
frb53-24-2 2 70 69.9 70 70 frb53-24-1 3 85 84.1 85 84.4 frb50-23-5 4 92 91.2 92 91.4
frb53-24-3 2 70 69.9 70 70 frb53-24-2 3 83 82 83 82.3 frb53-24-1 4 98 97.9 99 98
frb53-24-4 2 69 68.9 69 69 frb53-24-3 3 83 82.9 83 83 frb53-24-2 4 95 94.6 95 94.8
frb56-25-1 2 75 74.1 75 74.3 frb53-24-4 3 83 82.8 84 83.1 frb53-24-3 4 97 96.2 97 96.3
frb56-25-2 2 75 74.4 75 74.5 frb53-24-5 3 82 81 82 81.3 frb53-24-4 4 96 95.3 96 95.6
frb56-25-3 2 74 73.1 74 73.5 frb56-25-1 3 89 88.9 89 89 frb53-24-5 4 94 93.3 94 93.6
frb56-25-4 2 73 73 74 73.1 frb56-25-2 3 89 88.4 89 88.7 frb56-25-2 4 102 101.6 102 102
frb56-25-5 2 74 73.1 74 73.2 frb56-25-3 3 88 86.9 88 87.3 frb56-25-3 4 101 100.1 101 100.4
frb59-26-2 2 79 78 79 78.4 frb56-25-4 3 87 86.3 87 86.5 frb56-25-5 4 101 99.9 101 100.2
frb59-26-3 2 77 76.9 78 77.2 frb56-25-5 3 87 86.7 87 86.9 frb59-26-1 4 107 106.8 108 107
frb59-26-4 2 78 77.1 78 77.6 frb59-26-1 3 93 92.3 93 92.4 frb59-26-2 4 108 106.8 108 107
frb59-26-5 2 78 77.8 78 77.9 frb59-26-3 3 93 91.8 93 92 frb59-26-3 4 106 105.9 107 106.2
gen400_p0.9_65 2 74 73.1 73 73 frb59-26-5 3 93 91.7 93 92.2 frb59-26-4 4 106 105.6 107 106.1
san400_0.7_2 2 32 32 33 32.1 keller6 3 92 91.2 93 93 frb59-26-5 4 106 105.2 107 105.8
san400_0.9_1 2 103 102.1 103 102.6 san400_0.7_2 3 47 46.4 47 47 keller6 4 117 114.8 117 115
brock800_1 3 30 29.3 30 29.9 san400_0.7_3 3 38 38 39 38.4 p_hat1500-2 4 107 106.8 107 107
brock800_3 3 30 29.9 30 30 brock800_1 4 34 33.8 34 34 san400_0.7_3 4 50 49.7 50 50
Tab.6  Experimental results of DCCplex and DCCplex-GDI on classic instances
Instances k DCCplex DCCplex-GDI Instances k DCCplex DCCplex-GDI Instances k DCCplex DCCplex-GDI
max avg max avg max avg max avg max avg max avg
bn-human-BNU*_1-bg 2 214 208.2 214 210.3 bn-human-BNU*_1-bg 3 226 221.6 226 223.1 bn-human-BNU*_2-bg 4 204 200.6 204 202.3
dbpedia-link 2 36 34.2 36 35.2 dbpedia-link 3 39 38.4 39 37.4 dbpedia-link 4 40 38.4 40 38.9
soc-twitter-higgs 2 73 73 73 70.4 soc-orkut 3 59 57.4 59 58.1 twitter_mpi 4 187 186.5 187 186.9
twitter_mpi 2 155 154.9 155 154.6 web-baidu-baike 3 33 26.3 33 22.4 web-wikipedia-growth 4 35 32.9 35 33.6
web-baidu-baike 2 33 26.3 33 26.5 wikipedia_link_en 3 48 28.5 48 24.8 wikipedia_link_en 4 48 26.9 50 20.2
wikipedia_link_en 2 46 26.8 46 26 bn-human-BNU*_1-bg 4 236 233.5 236 234.6
Tab.7  Experimental results of DCCplex and DCCplex-GDI on sparse instances
Instances k KLS DCCplex-GDI Instances k KLS DCCplex-GDI Instances k KLS DCCplex-GDI
max max max max max max
C2000.9 2 93 94 frb100-40 4 177 180 frb100-40 5 200 201
frb100-40 2 129 130 frb50-23-4 4 92 91 frb50-23-2 5 103 104
frb53-24-5 2 69 68 frb59-26-5 4 107 106 frb50-23-5 5 103 104
frb100-40 3 154 156 C1000.9 5 122 121 frb53-24-1 5 111 112
frb50-23-3 3 77 76 C2000.5 5 29 28 frb53-24-2 5 107 108
frb56-25-1 3 89 90 C2000.9 5 137 136 frb53-24-5 5 105 106
brock800_4 4 34 33 C500.9 5 104 103 frb56-25-2 5 115 116
C1000.9 4 110 109 hamming10-2 5 515 516 frb59-26-1 5 121 122
C2000.5 4 26 25 hamming10-4 5 80 79 frb59-26-2 5 121 122
C4000.5 4 28 27 keller6 5 126 125 frb59-26-3 5 120 121
hamming10-4 4 70 69 p_hat1500-3 5 165 164
Tab.8  Experimental results of DCCplex-GDI and KLS on all the benchmarks
Instances k CFS-RLE DCCplex-GDI Instances k CFS-RLE DCCplex-GDI Instances k CFS-RLE DCCplex-GDI
max max max max max max
brock400_3 2 30 31 C2000.5 3 22 23 keller6 4 112 117
brock400_4 2 31 33 C2000.9 3 108 109 san400_0.7_1 4 80 81
C2000.5 2 19 20 keller6 3 92 93 hamming10-2 5 512 516
C2000.9 2 92 94 C4000.5 4 26 27 MANN_a81 5 3030 3240
gen400_p0.9_75 2 79 80 DSJC1000.5 4 23 24 san400_0.5_1 5 35 36
san1000 2 17 18 hamming8-2 4 128 130
san400_0.7_2 2 32 33 hamming10-4 4 68 69
Tab.9  Experimental results of DCCplex-GDI and CFS-RLE on all the benchmarks
Problem #inst Algorithm vs. GPsea1 vs. GPsea2
#better #worse #better #worse
Classic instances
MQCP187N-GDI53102
MKKP363F-GDI159253
MKKP363D-GDI116156
Problem#instAlgorithmvs. GPstr1vs. GPstr2
#better#worse#better#worse
Sparse instances
MQCP362N-GDI148155
MKKP303F-GDI2110
MKKP303D-GDI2141
Tab.10  Comparative results for our proposed methods and their modified versions with different strategies on all benchmarks
  
  
  
1 N, Malod-Dognin R, Andonov N Yanev . Maximum cliques in protein structure comparison. In: Proceedings of the 9th International Symposium on Experimental Algorithms. 2010, 106−117
2 J K Hao . Memetic algorithms in discrete optimization. In: Neri F, Cotta C, Moscato P, eds. Handbook of Memetic Algorithms. Berlin: Springer, 2012, 73−94
3 N, Alduaiji A, Datta J Li . Influence propagation model for clique-based community detection in social networks. IEEE Transactions on Computational Social Systems, 2018, 5( 2): 563–575
4 G, Ouyang D K, Dey P Zhang . Clique-based method for social network clustering. Journal of Classification, 2020, 37( 1): 254–274
5 S, Shahinpour S Butenko . Algorithms for the maximum k-club problem in graphs. Journal of Combinatorial Optimization, 2013, 26( 3): 520–554
6 H, Jiang F, Xu Z, Zheng B, Wang W Zhou . A refined upper bound and inprocessing for the maximum k-plex problem. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 2023, 5613−5621
7 J, Chen S, Cai S, Pan Y, Wang Q, Lin M, Zhao M Yin . NuQClq: An effective local search algorithm for maximum quasi-clique problem. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 12258−12266
8 J, Gao Z, Xu R, Li M Yin . An exact algorithm with new upper bounds for the maximum k-defective clique problem in massive sparse graphs. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 10174−10183
9 B Balasundaram . Graph theoretic generalizations of clique: optimization and extensions. Texas A&M University, Dissertation, 2007
10 D, Kempe J, Kleinberg É Tardos . Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 137−146
11 L, Terveen W, Hill B Amento . Constructing, organizing, and visualizing collections of topically related web resources. ACM Transactions on Computer-Human Interaction, 1999, 6( 1): 67–94
12 H, Yu A, Paccanaro V, Trifonov M Gerstein . Predicting interactions in protein networks by completing defective cliques. Bioinformatics, 2006, 22( 7): 823–829
13 S, Bandyopadhyay M Bhattacharyya . Mining the largest quasi-clique in human protein interactome. Nature Precedings, 2012,
https://doi.org/10.1038/npre.2012.7125.1
14 M Yannakakis . Node-and edge-deletion NP-complete problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing. 1978, 253−264
15 J M, Bourjolly G, Laporte G Pesant . An exact algorithm for the maximum k-club problem in an undirected graph. European Journal of Operational Research, 2002, 138( 1): 21–28
16 B, Balasundaram S, Butenko I V Hicks . Clique relaxations in social network analysis: the maximum k-plex problem. Operations Research, 2011, 59( 1): 133–142
17 J, Pattillo A, Veremyev S, Butenko V Boginski . On the maximum quasi-clique problem. Discrete Applied Mathematics, 2013, 161( 1−2): 244–257
18 Y, Peng Y, Xu H, Zhao Z, Zhou H Han . Most similar maximal clique query on large graphs. Frontiers of Computer Science, 2020, 14( 3): 143601
19 Z, Wang Y, Zhou C, Luo M Xiao . A fast maximum k-plex algorithm parameterized by the degeneracy gap. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 2023, 5648−5656
20 Z, Miao B Balasundaram . An ellipsoidal bounding scheme for the quasi-clique number of a graph. INFORMS Journal on Computing, 2020, 32( 3): 763–778
21 N, Daemi J S, Borrero B Balasundaram . Interdicting low-diameter cohesive subgroups in large-scale social networks. INFORMS Journal on Optimization, 2022, 4( 3): 304–325
22 M T, Almeida F D Carvalho . Two-phase heuristics for the k-club problem. Computers & Operations Research, 2014, 52: 94–104
23 E, Moradi B Balasundaram . Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optimization Letters, 2018, 12( 8): 1947–1957
24 J, Chen Y, Wang S, Cai M, Yin Y, Zhou J Wu . NukCP: an improved local search algorithm for maximum k-club problem. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 10146−10155
25 Y, Zhou J K Hao . Frequency-driven tabu search for the maximum s-plex problem. Computers & Operations Research, 2017, 86: 65–78
26 P, Chen H, Wan S, Cai J, Li H Chen . Local search with dynamic-threshold configuration checking and incremental neighborhood updating for maximum k-plex problem. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence. 2020, 2343−2350
27 W Pullan . Local search for the maximum k-plex problem. Journal of Heuristics, 2021, 27( 3): 303–324
28 Y, Jin J H, Drake K, He U Benlic . Reinforcement learning based coarse-to-fine search for the maximum k-plex problem. Applied Soft Computing, 2022, 131: 109758
29 Y, Djeddi H A, Haddadene N Belacel . An extension of adaptive multi-start tabu search for the maximum quasi-clique problem. Computers & Industrial Engineering, 2019, 132: 280–292
30 Q, Zhou U, Benlic Q Wu . An opposition-based memetic algorithm for the maximum quasi-clique problem. European Journal of Operational Research, 2020, 286( 1): 63–83
31 B Q, Pinto C C, Ribeiro J A, Riveaux I Rosseti . A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy. RAIRO-Operations Research, 2021, 55: S741–S763
32 A, Lipowski D Lipowska . Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and Its Applications, 2012, 391( 6): 2193–2196
33 Q, Wu J K Hao . A review on algorithms for maximum clique problems. European Journal of Operational Research, 2015, 242( 3): 693–709
34 S, Cai J, Lin C Luo . Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess. Journal of Artificial Intelligence Research, 2017, 59: 463–494
35 M E J, Newman M Girvan . Finding and evaluating community structure in networks. Physical Review E, 2004, 69( 2): 026113
36 V D, Blondel J L, Guillaume R, Lambiotte E Lefebvre . Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008( 10): P10008
37 M, López-Ibáñez J, Dubois-Lacoste L P, Cáceres M, Birattari T Stützle . The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives, 2016, 3: 43–58
38 D S, Johnson M A Trick . Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11−13, 1993. Boston: American Mathematical Society, 1996
39 K, Xu F, Boussemart F, Hemery C Lecoutre . Random constraint satisfaction: Easy generation of hard (satisfiable) instances. Artificial Intelligence, 2007, 171( 8-9): 514–534
40 T A, Davis Y Hu . The university of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 2011, 38( 1): 1
41 R A, Rossi N K Ahmed . The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 4292−4293
42 Y, Wang S, Cai J, Chen M Yin . SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem. Artificial Intelligence, 2020, 280: 103230
43 L, Jiang D, Ouyang Q, Zhang L Zhang . DeciLS-PBO: an effective local search method for pseudo-Boolean optimization. Frontiers of Computer Science, 2024, 18( 2): 182326
44 S, Pan Y, Ma Y, Wang Z, Zhou J, Ji M, Yin S Hu . An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem. Frontiers of Computer Science, 2023, 17( 4): 174326
[1] Shiwei PAN, Yiming MA, Yiyuan WANG, Zhiguo ZHOU, Jinchao JI, Minghao YIN, Shuli HU. An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem[J]. Front. Comput. Sci., 2023, 17(4): 174326-.
[2] Feidiao YANG, Wei CHEN, Jialin ZHANG, Xiaoming SUN. Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization[J]. Front. Comput. Sci., 2021, 15(5): 155404-.
[3] Yi CHU, Chuan LUO, Shaowei CAI, Haihang YOU. Empirical investigation of stochastic local search for maximum satisfiability[J]. Front. Comput. Sci., 2019, 13(1): 86-98.
[4] Wenting ZHAO, Lijin WANG, Yilong YIN, Bingqing WANG, Yuchun TANG. Sequential quadratic programming enhanced backtracking search algorithm[J]. Front. Comput. Sci., 2018, 12(2): 316-330.
[5] Wei-Neng CHEN, Da-Zhao TAN. Set-based discrete particle swarm optimization and its applications: a survey[J]. Front. Comput. Sci., 2018, 12(2): 203-216.
[6] Peng ZHANG. Unbalanced graph cuts with minimum capacity[J]. Front. Comput. Sci., 2014, 8(4): 676-683.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed