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

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

Quick Algorithm to Find an Approximate Maximum Clique in Undirected Graph by Using Local-limited Search Strategy

Finding the maximum clique is a well-known NP-complete problem,and the classical algorithms of finding the maximum clique basically use the exact search strategy.Because of the complexity of the NP-complete problem,these algorithms may only be applicable to some special small scale graphs,which are difficult to applied to the complex graphs with large scale vertices and edges.In this paper,aiming at the problem of executing much redundant and ineffective search after finding a maximum clique by using these classical algorithms,this paper proposed a new algorithm based on the partition&recursive and the local-limited search strategy to find a maximum clique in an undirected graph,that is,partitioning a graph into an adjacent sub-graph and suspended sub-graph,then finding recursively the maximum clique of the adjacent sub-graph and that of parts of sub-graph of the suspended sub-graph by setting a search range control function.The experiments in a benchmark data set DIMACS show that this algorithm can find the maximum clique in most of the experimental data,can find the approximate maximum clique in other experimental data that is very close to the maximum clique,and it is much faster than these classical algorithm.Therefore,in many cases with non-precise requirements for the maximum clique,this algorithm has better application value.