Page 434 - 《软件学报》2024年第6期

3010 软件学报 2024 年第 35 卷第 6 期

BA MA1 MA2
100
95
90
近似解/精确解 (%) 80
85
75
70
65
60
55
50
Primary High Email Bills Math DAWN NDC Stack MAG DBLP

图 10 准确率

总的来说, BA 算法只能搜索到一个不太准确的超图最大独立集, 但其运行时间非常短. MA1 和 MA2 算法的
on Discrete Algorithms. Arlington: SIMA, 1994. 365–371.
运行时间要长一些, 但可以保证有很高的准确率. 在小规模图上, one-degree 点剪枝比 high-degree 剪枝耗时, 但在
大规模图上, one-degree 点剪枝可以在保证精确的情况下, 更快的削减原图的大小, 从而加速 high-degree 剪枝的效
率. 因此 MA1 算法适合在较小规模的图上搜索, 其准确率与 MA2 算法接近, 但时间更短. 而包含 one-degree 点剪
枝的 MA2 算法更适合在较大规模的图, 此时其准确率和运行效率均优于 MA1 算法.
9 结论及未来工作

本文基于普通图上的独立集定义提出一种面向超图的独立集和最大独立集的定义. 本文又通过观察分析, 提
出超图最大独立集搜索的两个原则, 并基于此, 提出了一种基于贪心策略的超图最大独立集基础算法. 进一步, 本
文分析了普通图上的最大独立集搜索方法, 提出了一种超图上的近似最大独立集搜索架构, 即精确剪枝与近似剪
枝相结合, 以精确剪枝缩小图的规模, 以近似剪枝加快搜索速度. 此外, 本文还基于该架构提出了 3 种精确剪枝策
略和一种启发式的近似剪枝策略, 将超图上的近似最大独立集搜索架构和 4 种剪枝策略相结合, 提出了一种改进
的超图近似最大独立集算法. 最后通过实验验证, 证明了改进算法虽然速度慢于基础算法, 但可以在线性时间内找
到比较接近于真实结果的近似最优解.
本文虽然实现了一种改进的超图最大独立集算法, 但是本文提出的精确剪枝策略仍主要是面向 one-degree 超
点和 one-size 超边. 而一些现有的普通图的近似最大独立集算法已经使用 two-degree 剪枝等更高阶的剪枝策略来
实现更高的准确率和速度. 下一步的工作将进一步分析超图独立集搜索过程中的高阶剪枝策略, 提高算法效率, 同
时将进一步研究算法近似率的理论保证.

References:
[1] Berman P, Fürer M. Approximating maximum independent set in bounded degree graphs. In: Proc. of the 5th Annual ACM-SIAM Symp.

[2] Fu AWC, Wu HH, Cheng J, Wong RCW. IS-Label: An independent-set based labeling scheme for point-to-point distance querying. Proc.
of the VLDB Endowment, 2013, 6(6): 457–468. [doi: 10.14778/2536336.2536346]
[3] Halldórsson MM, Radhakrishnan J. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica,
1997, 18(1): 145–163. [doi: 10.1007/BF02523693]
[4] Robson JM. Algorithms for maximum independent sets. Journal of Algorithms, 1986, 7(3): 425–440. [doi: 10.1016/0196-6774(86)90032-
5]
[5] Puthal D, Nepal S, Paris C, Ranjan R, Chen JJ. Efficient algorithms for social network coverage and reach. In: Proc. of the 2015 IEEE Int’l
Congress on Big Data. New York: IEEE, 2015. 467–474. [doi: 10.1109/BigDataCongress.2015.75]
[6] Basagni S. Finding a maximal weighted independent set in wireless networks. Telecommunication Systems, 2001, 18(1–3): 155–168.