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

• 作者: 何雄 江超 罗远胜 钟茂生 陶兰
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 近似最大团 求解算法 邻接子图 悬挂子图 局部有限搜索
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 计算机科学理论
• 页码范围: 72-78
• 页数: 7页
• 分类号: TP301.6
• 字数: 7308字
• 语种: 中文
• DOI: 10.11896/jsjkx.181102109

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	钟茂生	江西师范大学计算机信息工程学院	29	165	7.0	11.0
5	罗远胜	江西财经大学网络信息管理中心	8	42	4.0	6.0
6	何雄	华东交通大学信息工程学院	4	4	1.0	2.0
7	江超	华东交通大学信息工程学院	2	0	0.0	0.0
8	陶兰	华东交通大学信息工程学院	1	0	0.0	0.0