基于局部有限搜索的无向图近似最大团快速求解算法

发布时间：2022-10-05 22:14

　　无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。 

【文章页数】：7 页

【文章目录】：
1 引言
2 相关工作
3 定义与定理
4 算法设计
    4.1 基本思想
    4.2 基于局部有限搜索的近似最大团求解算法
5 实验及结果


【参考文献】：
期刊论文
[1]求解最大团问题的并行多层图划分方法[J]. 顾军华,霍士杰,武君艳,尹君,张素琪.  计算机应用. 2018(12)
[2]大规模稀疏图的极大团枚举算法[J]. 何琨,邹晟昊,周建荣.  华中科技大学学报(自然科学版). 2017(12)
[3]基于蚁群优化算法求解最大团问题的研究[J]. 尹皓,宋晗.  南华大学学报(自然科学版). 2017(03)
[4]顶点加权最大团问题的加权分治算法[J]. 黄飞,宁爱兵,刘志民,何咏梅,王永斐,张惠珍.  数学理论与应用. 2017(02)
[5]关于最大团问题的一种新算法[J]. 贾晓峰,郭廷花,续晓欣.  中北大学学报(自然科学版). 2006(02)
[6]求解图的最大团的一种算法[J]. 仲盛,谢立.  软件学报. 1999(03)



本文编号：3686602