文献类型：期刊文章

作　　者：钟茂生[1,2] 江超[2] 陶兰[2] 何雄[2] 罗远胜[3]

ZHONG Mao-sheng;JIANG Chao;TAO Lan;HE Xiong;LUO Yuan-sheng(School of Computer&Information Engineering,Jiangxi Normal University,Nanchang 330022,China;School of Information Engineering,East China Jiaotong University,Nanchang 330013,China;Center of Network Information Management,Jiangxi University of Finance and Economics,Nanchang 330013,China)

机构地区：[1]江西师范大学计算机信息工程学院,南昌330022 [2]华东交通大学信息工程学院,南昌330013 [3]江西财经大学网络信息管理中心,南昌330013

出　　处：《计算机科学》

基　　金：国家自然科学基金(61877031,61462027,61562031);江西省教育厅科技计划项目(GJJ170206)~~

年　　份：2020

卷　　号：47

期　　号：1

起止页码：72-78

语　　种：中文

收录情况：BDHX、BDHX2017、CSA、CSCD、CSCD_E2019_2020、IC、JST、RCCSE、UPD、ZGKJHX、核心刊

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

关 键 词：近似最大团  求解算法  邻接子图  悬挂子图  局部有限搜索  

分 类 号：TP301.6]