基于邻接点求解最大团问题  

Solving Maximum Clique Problem Based on Adjacent Points

作　　者：张丽娟[1] 王莹港 杨燕[1] 王鑫楷 

机构地区：[1]云南大学,云南 昆明

出　　处：《计算机科学与应用》2020年第9期1655-1662,共8页Computer Science and Application

摘　　要：由于最大团问题(maximum clique problem, MCP)的复杂性、挑战性,以及在数据挖掘等各个领域的广泛应用,使得在计算机科学领域求解MCP问题具有非常重要的意义。本文通过介绍最大团问题以及研究意义,描述了最大团问题的研究现状,指出目前精确性算法和启发式算法解决最大团问题存在的不足,根据最大团中两两节点间均有边相连的性质提出了基于邻接点求解最大团算法,并论证该算法的正确性和完整性,最后将此算法应用于包含任意节点求其最大团的问题。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.

关 键 词：最大团问题(MCP) 邻接点 NP完全问题 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]