基于邻接点求解最大团问题
Solving Maximum Clique Problem Based on Adjacent Points
DOI: 10.12677/CSA.2020.109175, PDF,    科研立项经费支持
作者: 张丽娟, 王莹港, 杨 燕, 王鑫楷：云南大学，云南 昆明
关键词: 最大团问题(MCP)；邻接点；NP完全问题；Maximum Clique Problem； Adjacency Point； NP Complete Problem
摘要: 由于最大团问题(maximum clique problem, MCP)的复杂性、挑战性，以及在数据挖掘等各个领域的广泛应用，使得在计算机科学领域求解MCP问题具有非常重要的意义。本文通过介绍最大团问题以及研究意义，描述了最大团问题的研究现状，指出目前精确性算法和启发式算法解决最大团问题存在的不足，根据最大团中两两节点间均有边相连的性质提出了基于邻接点求解最大团算法，并论证该算法的正确性和完整性，最后将此算法应用于包含任意节点求其最大团的问题。
Abstract: The maximum clique problem (MCP) is a significant problem in computer science field because of its complexity, challenging and extensive applications in data mining and other fields. This paper first briefly introduces the maximum clique problem and its research significance, then describes the research status of the maximum clique problem, and points out the deficiencies of the current deterministic algorithm and heuristic algorithm to solve the maximum clique problem. An algorithm for solving maximum clique based on adjacent points is presented according to the nature of edge connection between two nodes in the maximum clique. Based on the nature of edge connection between two nodes in the maximum clique, an algorithm for solving the maximum clique based on adjacent points is proposed, and its correctness and integrity are demonstrated. Finally, the algorithm is applied to the problem of finding the maximum clique containing any node.
文章引用：张丽娟, 王莹港, 杨燕, 王鑫楷. 基于邻接点求解最大团问题[J]. 计算机科学与应用, 2020, 10(9): 1655-1662. https://doi.org/10.12677/CSA.2020.109175

参考文献

[1] 贾晓峰, 朱必文. 一类图中的最大团[J]. 系统科学与数学, 1998, 8(3): 226-233.
[2] 马红平, 贾晓峰. 一类循环图中的最大团[J]. 华北工学院学报, 2001, 22(5): 384-386.
[3] 黄培铣, 邓国勋, 王化等. 一类循环图的最大团与最大独立集[J]. 广西师范大学(自然科学版), 1992, 10(1): 12-15.
[4] 戎文晋, 贾晓峰. 关于无爪图最大团数的一个估计[J]. 太原理工大学学报(自然科学版), 2002, 33(6): 676-677.
[5] Adleman, L.M. (1994) Molecular Computa-tion of Solution to Combinatorial Optimization. Science, 226, 1021-1024. [Google Scholar] [CrossRef] [PubMed]
[6] Loukakis, E. and Tsouros, C. (1981) A Depth First Search Algorithm to Generate the Family of Maximal Independent Sets of a Graph Lexicographically. Computing, 27, 349-366. [Google Scholar] [CrossRef] 
[7] Enet, S. and Solnon, C. (2003) Searching for Maximum Cliques with Ant Colony Optimization. Applications of Evolutionary Computing. Springer, Berlin Heidelberg, 236-245. [Google Scholar] [CrossRef] 
[8] Furtado, P. and Madeira, H. (2000) Vmhist: Efficient Multidimen-sional Histograms with improved Accuracy. Proceedings of the 2nd International Conference on Data Warehousing and Knowledge Discovery (DaWak 2000), London, 4-6 September 2000, 431-436. [Google Scholar] [CrossRef] 
[9] Srinivas, M.A., Gardner, P.C. and Ballard, D.H. (1987) Graph Problems and Connectionist Architectures. Technical Report TR 167, University of Rochester, Rochester.
[10] Geng, X., Xu, J., Xiao, J., et al. (2007) A Simple Simulated Annealing Algorithm for the Maximum Clique Problem. Information Sciences, 177, 5064-5071. [Google Scholar] [CrossRef] 
[11] Aarts, E. and Korst, J. (1989) Simulated Annealing and Boltzmann Machines, John Wiley& Sons, Chichester.
[12] Tomita, E. and Seki, T. (2003) An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique. Proceedings of Discrete Mathematics and Theoretical Computer Science, 2731, 278-289. [Google Scholar] [CrossRef] 
[13] Tomita, E. and Kameda, T. (2007) An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments. Journal of Global Optimization, 37, 95-111. [Google Scholar] [CrossRef] 
[14] Konc, J. and Janezic, D. (2007) An Improved Branch and Bound Algorithm for the Maximum Clique Problem. Communications in Mathematical and in Computer Chemistry, 58, 569-590.
[15] Tomita, E., Sutani, Y., Higashi, T., et al. (2010) A Simple and faster Branch-and-Bound Algorithm for Finding a Maximum Clique. Proceedings of WALCOM: Algorithms and Computation, 4th International Workshop, WALCOM 2010, Dhaka, 10-12 February 2010, 191-203. [Google Scholar] [CrossRef] 
[16] Li, C.M., Fang, Z.W. and Xu, K. (2013) Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem. 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, 4-6 November 2013, 939-946. [Google Scholar] [CrossRef] 
[17] San Segundo, P., Nikolaev, A. and Batsyn, M. (2015) Infra-Chromatic Bound for Exact Maximum Clique Search. Computers & Operations Research, 64, 293-303. [Google Scholar] [CrossRef]