关键词: 最大团问题（MCP）, 顶点度数, NP完全问题

Abstract: The maximum clique problem (MCP) is a significant problem in computer science field because of its complexity, challenging and the extensive applications in data mining and other fields. This paper puts forward a new degree-based approach to finding the maximum clique in a given graph G. According to the characteristic that the degree of the vertexes in a maximum clique is relatively larger, the new approach solves the maximum clique by starting from the first vertex which degree is the largest in the graph G. In order to further improve the efficiency of the algorithm, this paper presents three improvement and pruning strategies based on the characteristics of the graph and the maximum clique. This paper proves that the new approach is correct and complete, the time complexity is[O(1.442n)], and the space cost is [O(n2)]. Finally, an empirical study verifies the effectiveness and efficiency of the new approach.

Key words: maximum clique problem (MCP), the degree of vertexes, NP complete problem