Page 268 - 《软件学报》2025年第8期

田新亮 等: 一种高效的求解最小负载着色问题的局部搜索算法 3691

表 A1 IRLTS 算法与 3 个对比算法的具体实验结果 (续)

GVNS MS-GVNS RLTS IRLTS
Graph |V|
best avg time (s) best avg time (s) best avg time (s) best avg time (s)
scc_rt_assad 2 035 30 30 0.351 526 30 30 0.529 732 30 30 48.256 3 30 30 3.896 31
tech-routers-rf 2 113 2 994 2 932.3 1 247.05 3 007 2 977.5 953.967 3 034 2 989.3 1 285.34 3 044 2 997.7 918.639
scc_rt+damascus 2 962 18 18 6.795 16 18 18 4.750 15 18 17.9 369.144 18 18 15.615 4
web-edu 3 031 3 205 3 194.8 432.876 3 207 3 199 714.809 3 204 3 202 1 307.75 3 212 3 205.2 805.874
scc_rt_obama 3 040 2 2 0.202 93 2 2 0.335 25 2 2 0.034 042 2 2 0.010 975
scc_rt_occupy 3 090 26 26 2.468 77 26 26 11.173 9 26 25.9 488.698 26 26 15.464
scc_rt_lebanon 3 370 2 2 0.487 716 2 2 0.566 18 2 2 5.548 38 2 2 0.048 443
scc_rt_tlot 3 513 4 4 0.864 37 4 4 1.592 26 4 4 115.462 4 4 2.480 09
scc_rt_occupywallstnyc 3 594 328 328 51.820 1 328 327.9 14.825 328 327.4 478.287 328 328 78.896 9
scc_rt_israel 3 686 6 6 0.754 021 6 6 1.042 22 6 6 21.980 6 6 6 0.439 326
scc_rt_gop 3 716 3 3 0.436 56 3 3 0.664 212 3 3 6.869 56 3 3 0.014 865
scc_rt_alwefaq 4 157 114 114 27.389 114 114 100.64 114 113.9 787.734 114 114 45.100 4
ca-GrQc 4 158 6 291 6 228.8 1 154.2 6 296 6 240.2 1 348.2 6 372 6 289.2 1 607.18 6 457 6 430.2 1 238.92
scc_rt_oman 4 452 5 5 0.624 796 5 5 1.192 85 5 5 35.021 4 5 5 0.374 704
scc_rt_tcot 4 506 9 9 4.690 63 9 9 4.855 66 9 9 25.800 6 9 9 1.100 14
scc_rt_bahrain 4 659 49 48.4 37.145 7 49 48.9 161.838 48 47.9 667.571 49 48.8 637.36
scc_rt_uae 4 757 6 6 1.900 99 6 6 2.195 19 6 6 14.788 5 6 6 1.191 63
web-spam 4 767 15 999 15 776.7 1 236.32 16 001 15 902.6 975.142 15 864 15 654 1 618.82 15 959 15 896.5 967.254
scc_rt_p2 4 785 7 7 0.773 178 7 7 1.486 63 7 7 10.850 8 7 7 0.025 6
inf-power 4 941 3 117 3 096.6 1 335.69 3 115 3 094.9 1 281.2 3 091 3 067.9 1 751.24 3 272 3 259.6 832.905
scc_rt_libya 5 021 11 11 11.757 6 11 11 8.698 16 11 10.5 156.416 11 11 5.471 65
scc_rt_http 5 691 1 1 0.463 592 1 1 1.495 63 1 1 0.074 111 1 1 0.030 362
scc_rt_ksa 5 775 8 8 19.644 7 8 8 45.905 1 8 7.5 399.028 8 8 10.745 3
scc_rt_dash 5 968 16 16 27.134 9 16 16 39.285 2 16 15.2 267.532 16 16 17.632 1
ca-Erdos992 6 100 3 461 3 409.7 1 647.55 3 460 3 415 1 284.71 3 462 3 379.6 1 702.85 3 556 3 525.7 1 364.03
socfb-MIT 6 402 96 166 96 065.6 771.581 96 224 96 114.9 767.943 94 824 94 022.3 1 401.37 96 324 95 782.3 1 090.64
socfb-CMU 6 621 97 886 97 421.6 1 019.58 97 995 97 282 872.456 97 673 95 765.7 1 508.31 98 333 97 793.1 1 378.25
scc_rt_qatif 6 718 5 5 2.561 36 5 5 3.652 22 5 5 97.732 1 5 5 0.322 374
scc_rt_saudi 6 805 30 30 84.926 4 30 30 45.685 30 29.2 250.653 30 30 46.104 6
ia-reality 6 809 3 625 3 442.6 1 776.06 3 671 3 441.1 1 723.1 3 655 3 643.5 1 072.24 3 709 3 689.5 1 136.8
scc_reality 6 809 1 481 5631.48E+06 376.127 1 481 6681.48E+06 385.83 1 481 6681.48E+06 385.83 1 493 5351.49E+06 1 216.98
bio-dmela 7 393 9 966 9 791.6 1 472.74 9 959 9 830.5 1 041.24 9 713 9 662.1 1 636.57 10 080 10 046.5 1 073.06
tech-WHOIS 7 476 24 076 23 807.1 919.897 24 175 23 882.5 749.322 23 160 22 886.1 1 552.31 23 456 23 232.5 948.36
scc_rt_onedirection 7 704 93 93 24.524 4 93 93 7.306 07 93 92.6 378.419 93 93 8.587 52
scc_rt_mittromney 7 850 48 48 206.992 48 48 141.92 43 42.7 321.16 48 47.9 658.531
scc_rt_gmanews 8 330 372 372 143.041 372 372 412.899 372 367.5 520.333 372 372 272.653
scc_twitter-copen 8 580 143 861 143 505 152.601 143 983 143 683 633.775 142 625 141 896 1 410.88 144 561 144 432 835.622
scc_rt_justinbieber 9 364 138 138 52.727 6 138 138 88.4 138 136.7 268.388 138 138 285.221
scc_rt_barachobama 9 551 87 87 90.681 5 87 87 76.407 7 87 84.2 506.641 87 87 11.643 8
scc_rt_lolgop 9 742 1 670 1 669.9 272.862 1 670 1 670 347.313 1 668 1 658.5 1 229.04 1 670 1 666 1 063.69
socfb-Duke14 9 885 200 002 199 176 110.891 199 939 198 851 88.696 206 795 202 648 1 796.41 207 089 204 951 380.834
scc_infect-dublin 10 972 87 096 86 558.4 971.972 87 085 86 710 738.878 86 814 86 332.1 1 799.55 87 357 86 801.4 1 127.91
ca-HepPh 11 204 53 493 52 311.1 1 197.16 53 272 52 275.9 1 050.87 46 203 45 664.1 1 799.58 47 414 46 835.2 1 029.91
web-indochina-2004 11 358 22 518 22 385.7 145.895 22 513 22 394.9 329.941 22 562 22 392.6 1 784.27 22 868 22 706.1 583.901
socfb-Stanford3 11 586 218 610 218 222 322.056 218 584 218 357 451.828 215 119 213 164 1 799.33 223 509 219 717 268.873
web-BerkStan 12 305 9 349 9 331.3 1 145.77 9 373 9 334.4 1 214.15 8 984 8 947.7 1 798.91 9 438 9 413.9 1 603.31
socfb-UCSB37 14 917 195 217 191 673 676.15 195 356 191 089 405.133 163 929 161 817 1 799.24 196 517 194 156 804.854
web-webbase-2001 16 062 12 459 12 356 1 765.74 12 496 12 381.1 1 776.32 9 696 9 540.7 1 799.18 12 465 12 308.7 834.545
socfb-Uconn 17 206 241 198 240 350 851.68 241 556 240 240 830.9 188 970 187 443 1 798.94 243 154 236 876 432.319