-
题名基于局部有限搜索的无向图近似最大团快速求解算法
被引量:3
- 1
-
-
作者
钟茂生
江超
陶兰
何雄
罗远胜
-
机构
江西师范大学计算机信息工程学院
华东交通大学信息工程学院
江西财经大学网络信息管理中心
-
出处
《计算机科学》
CSCD
北大核心
2020年第1期72-78,共7页
-
基金
国家自然科学基金(61877031,61462027,61562031)
江西省教育厅科技计划项目(GJJ170206)~~
-
文摘
无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。
-
关键词
近似最大团
求解算法
邻接子图
悬挂子图
局部有限搜索
-
Keywords
Approximate maximum clique
Finding algorithm
Adjacent sub-graph
Suspended sub-graph
Local-limited search
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-