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

3692 软件学报 2025 年第 36 卷第 8 期

表 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)
ca-AstroPh 17 903 84 743 84 059.1 1 184.88 84 718 84 236.5 1 380.05 70 004 69 017.1 1 798.81 84 398 83 295.5 702.451
scc_retweet 18 469 23 929 23 850.4 1 153.27 23 931 23 871.3 963.443 23 238 23 011.6 1 576.7 23 509 23 429.3 1 040.42
socfb-UCLA 20 453 297 857 297 632 1 747.67 297 891 297 570 1 696.57 228 443 223 907 1 799.18 302 939 300 062 748.105
ca-CondMat 21 363 40 538 40 401 1 680.06 40 582 40 270.2 1 702.69 29 103 28 916 1 798.62 40 624 40 056.9 1 416.76
socfb-Berkeley13 22 900 335 388 335 108 1 664.1 335 650 334 978 1 739.75 241 661 239 034 1 798.55 335 001 333 342 254.17
socfb-Wisconsin87 23 831 332 110 324 438 1 497.43 330 792 325 030 1 459.98 237 930 236 161 1 798.55 332 495 329 405 360.272
tech-as-caida2007 26 475 22 254 21 579.3 1 794.99 22 346 21 878 1 787.48 15 761 15 562.8 1 797.88 22 828 22 175.7 1 581.78
soc-epinions 26 588 42 309 42 029.2 1 793.39 42 293 42 019.4 1 791.28 31 843 31 344.9 1 798.48 43 448 41 597.7 1 027.66
socfb-Indiana 29 732 525 273 523 775 487.74 525 284 524 618 640.503 348 112 345 554 1 798.1 524 038 520 644 565.095
socfb-Uillinois 30 795 503 654 502 679 515.352 503 252 502 384 543.957 339 412 336 811 1 796.74 514 123 507 966 632.508
ia-email-EU 32 430 22 377 22 056.4 1 758.23 22 177 21 883.3 1 759.53 16 171 15 996.4 1 798.06 23 310 22 939.6 1 163.54
ia-enron-large 33 696 75 810 73 915.8 1 795.45 75 963 73 844 1 790.07 50 093 49 768.2 1 795.14 77 220 75 643.4 687.118
socfb-UF 35 111 572 593 571 216 1 583.62 572 109 571 256 1 448.53 377 413 376 160 1 795.25 583 203 575 653 888.747
socfb-Texas84 36 364 598 625 595 042 1 792.26 597 885 594 984 1 797.86 404 704 402 492 1 792.37 597 446 594 262 566.696
tech-internet-as 40 164 35 986 34 731.2 1 784.82 35 889 34 828.3 1 778.34 22 663 22 576.8 1 796.15 36 852 34 969.5 1 583
socfb-Penn94 41 536 538 265 535 965 1 743.82 539 270 535 802 1 756.11 344 303 342 776 1 783.59 547 446 539 845 649.422
sc-nasasrb 54 870 639 862 634 755 1 390.57 637 975 631 671 1 789.37 330 305 329 221 1 789.57 642 004 633 975 1 670.38
soc-brightkite 56 739 92 118 90 939.6 1 795.72 91 910 91 132.3 1 790.73 54 401 54 001.9 1 759.43 95 116 92 361.3 1 043.95

田新亮(1991－), 男, 博士, 主要研究领域为组合 蒋璐宇(1998－), 女, 博士生, CCF 学生会员, 主
优化, 算法设计与分析. 要研究领域为可满足性问题, 组合优化问题.

欧阳丹彤(1968－), 女, 博士, 教授, 博士生导师, 太然(1997－), 男, 博士生, 主要研究领域为基于
CCF 高级会员, 主要研究领域为自动推理, 基于 模型的诊断.
模型的诊断.

周慧思(1995－), 女, 博士, CCF 专业会员, 主要 张立明(1980－), 男, 博士, CCF 高级会员, 主要
研究领域为基于模型的诊断, SAT 问题. 研究领域为 SAT 问题, 基于模型的诊断.