最大团问题降阶算法

Reduction Algorithm for Maximum Clique Problem

最大团问题是找出给定图中的一个最大结点子集合,使得子集合中的任意两点之间都有边相连,最大团问题是一个著名的NP-难题,在很多领域中都有着广泛的应用.本文在研究最大团问题数学性质的基础上给出该问题的一个初步降阶方法;在初步降阶的基础上给出一个求解最大团问题的上、下界方法;最后将降阶方法和上下界方法结合起来形成一个全新的降阶算法,该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.在文中还介绍了本算法和其它各类算法的优缺点,最后通过多个示例来进一步说明算法的原理及应用情况.

Given a graph, in the maximum clique problem, one desires to find the largest number of vertices, any two of which are adjacent. The maximum clique problem（ MCP） is a well-known NP-hard problem and has many applications in various fields. Based on the mathematical properties of MCP, a preliminary reduction algorithm is presented here. Then the upper and lower bound of the problem can be found after using the preliminary reduction algorithm. Finally a new reduction algorithm for maximum clique problem was proposed by combing the first two technologies. The reduction algorithm not only can be used alone, but also can be used by cooperating with othter algorithms to get more effective results. This paper also introduces the advantages and disadvantages of the reduction algorithm and other algorithms. Several instances were solved and analyzed here to illustrate the principles and application of the algorithm further.