计算机科学 ›› 2020, Vol. 47 ›› Issue (1): 72-78.doi: 10.11896/jsjkx.181102109
钟茂生1,2,江超2,陶兰2,何雄2,罗远胜3
ZHONG Mao-sheng1,2,JIANG Chao2,TAO Lan2,HE Xiong2,LUO Yuan-sheng3
摘要: 无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。
中图分类号:
[1]LUCE R D,PERRY A D.A method of matrix analysis of group structure [J].Psychometrika,1949,14(2):95-116. [2]GAREY M R,JOHNSON D S.Computers and Intractability:A guide to the Theory of NP-Completeness [M]∥Computers and Intractability:A Guide to the Theory of NP-Completeness.New York:Freeman,1979. [3]PATRICK P.Exact Algorithms for Maximum Clique:A Computational Study[J].Algorithms,2012,5(4):545-587. [4]PAULL M C,UNGER S H.Minimizing the Number of States in Incompletely Specified Sequential Switching Functions[J].IRE Transactions on Electronic Computers,1959,EC-8(3):356-367. [5]Bonner R E.On some clustering techniques[J].IBM Journal of Research and Development,1964,8(1):22-32. [6]BEDNAREK A R,TAULBEE O E.On maximal chains[J].Re- vue Roumaine des Mathematiques Pures et Appliquees,1966,11(1):23-25. [7]PARDOLOS P M,RODGERS G P.A branch and bound algorithm for the maximum clique problem[J].Computer & OR,1992,19:363-375. [8]TOMITA E,SEKI T.An efficient branch-and-bound algorithm for finding a maximum clique and computational experiments[M]∥Discrete Mathematics and Theoretical Computer Science.Berlin:Springer,2003:278-289. [9]KONC J.An improved branch and bound algorithm for the maximum clique problem[J].MATCH Commun.in Mathematical and in Computer Chemistry,2007,58(3):569-590. [10]SEGUNDO P S,TAPIA C.A new Implicit Branching Strategy for Exact Maximum Clique[C]∥XXII IEEE International Conference onTools with Artificial Intelligence (ICTAI).IEEE,2010:352-357. [11]TOMITA E,SUTANI Y,HIGASHI T,et al.A Simple and Faster Branch-and-Bound Algorithm for Finding Maximum Clique[M]∥WALCOM:Algorithms and Computation.Berlin:Sprin-ger,2010:191-203. [12]PATTABIRAMAN B,PATWARY M M A,GEBREMEDHIN A H,et al.Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection[J].Internet Mathematics,2015,11(4/5):421-448. [13]MIKHAIL B,BORIS G,EVGENY M,et al.Improvements to MCS algorithm for the maximum clique problem[J].Journal of Combinatorial Optimization,2014,27(2):397-416. [14]MCCREESH C,PROSSER P.Reducing the Branching in a Branch and Bound Algorithm for the Maximum Clique Problem[C]∥International Conference on Principles and Practice of Constraint Programming.Cham:Springer,2014. [15]ÖSTERG;ÅRD,PATRIC R J.A fast algorithm for the maximum clique problem[M].Elsevier Science Publishers B.V.,2002. [16]RÉGIN J C.Using Constraint Programming to Solve the Maximum Clique Problem[C]∥International Conference on Principles & Practice of Constraint Programming.Springer Berlin Heidelberg,2003. [17]LI C M,QUAN Z.An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem[C]∥Twenty-fourth Aaai Conference on Artificial Intelligence.DBLP,2010. [18]LI C M,FANG Z,XU K.Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem[C]∥2013 IEEE 25th International Conference on Tools with Artificial Intelligence.IEEE,2014. [19]BOMZE I M,BUDINICH M,PARDALOS P M,et al.The maximum clique problem [M]∥Handbook of Combinatorial Optimization 4.Kluwer Academic Publishers,1999:1-74. [20]FEO T A,RESENDE M G C,SMITH S H.A Greedy Randomi- zed Adaptive Search Procedure for Maximum Independent Set[J].Operations Research,1994,42(5):860-878. [21]BUI T N,EPPLEY P H.A Hybrid Genetic Algorithm for the Maximum Clique Problem[C]∥International Conference on Genetic Algorithms.DBLP,1995. [22]MARCHIORI E.Genetic,Iterated and Multistart Local Search for the Maximum Clique Problem[C]∥Applications of Evolutionary Computing,EvoWorkshops 2002.Berlin:Springer,2002. [23] ZHANG Q,SUN J,TSANG E.An Evolutionary Algorithm With Guided Mutation for the Maximum Clique Problem[J].IEEE Transactions on Evolutionary Computation,2005,9(2):192-200. [24]BUI T N,JR J R R.Finding Maximum Cliques with Distributed Ants[J].Gecco Lecture Notes in Computer Science,2004,3102:24-35. [25]YIN H,SONG H.The Research of Ant Colony Optimization Algorithm for Maximum Clique Problem[J].Journal of University of South China(Science and Technology),2017,31(3):81-85. [26]SEGUNDO P S,DIEGO R L,JIMÉNEZ A.An exact bit-parallel algorithm for the maximum clique problem[J].Computers & Operations Research,2011,38:571-581. [27]XIANG J,GUO C,ABOULNAGA A.Scalable maximum clique computation using MapReduce[C]∥2013 IEEE 29th International Conference on Data Engineering (ICDE).IEEE,2013. [28]MCCREESH C,PROSSER P.Multi-Threading a State-of-the- Art Maximum Clique Algorithm[J].Algorithms,2013,6(4):618-635. [29]GU J H,HUO S J,WU J Y,et al.Parallel multi-layer graph partitioning method for solving maximum clique problems[J].Journal of Computer Applications,2018,38(12):3425-3432. [30]MCCREESH C,PROSSER P.The Shape of the Search Tree for the Maximum Clique Problem,and the Implications for Parallel Branch and Bound[J].Acm Transactions on Parallel Computing,2014,2(1):1-27. [31]ZHONG S,XIE L.An Algorithm Computing the Maximum Clique in a Graph[J].Journal Of Software,1999,10(3):288-292. [32]LI Y.Genetic algorithm in DNA computing:A solution to the maximal clique problem[J].Chinese Science Bulletin,2004,49(9):967. [33]ZHOU X D,SUN C Y,LI W J.Solving Maximum Clique Problem by MEC[C]∥Advance of China Artificial Intelligence (2003).Beijing:Beijing University of Post and Telecommunication,2003. [34]JIA X F,GUO T H,XU X X.A New Algotithm for the Maximum Clique Problem[J].Journal of North University of China(Natural Science Edition),2006,27(2):180-182. [35]HE K,ZOU S H,ZHOU J R.Enumerating maximal cliques in large sparse graphs[J].Journal of Huazhong & Technology (Natural Science Edition),2017,45(12):1-6. [36]HUANG F,NING A B,LIU Z M,et al.Measure and Conquer Approach for the Maximum Vertex Weightet Clique Problem[J].Mathematical Theory and Applications,2017,37(2):97-104. |
[1] | 许少华 庞跃武 何新贵. 一种基于过程神经网络的动态系统控制信号求解模型和算法 Control Signal Solving Model and Algorithm of Dynamic System Based on Process Neural Network 计算机科学, 2012, 39(1): 159-161. |
[2] | 郭平 侯睿 杨国洲 范丽. 方位关系约束满足问题的推理求解 计算机科学, 2005, 32(8): 170-172. |
[3] | 黄文奇 陈端兵. 一种求解矩形块布局问题的拟物拟人算法 计算机科学, 2005, 32(11): 182-186. |
[4] | 徐周波 古天龙 赵岭忠. 网络最大流问题求解的符号ADD增广路径算法 计算机科学, 2005, 32(10): 38-40. |
[5] | 李韶华 张健. Survey Propagation:一种求解SAT的高效算法 计算机科学, 2005, 32(1): 132-137. |
|