Reduction Algorithm for Maximum Clique Problem
Yinglei Wang · Journal of Chinese Computer Systems · 2013
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.