| The maximum clique problem (MCP) is a classical problem in combinatorial optimization. This thesis summarizes the related previous studies including its application, estimation of bounds, and researches on various algorithms.The thesis elaborates the bound of MCP and gets a good upper bound at first, then focuses the division of adjacent vertices set and MCP in detail. The division of adjacent vertices set reduces the domain of problem(the selection of parameter and application of average degree reduce the domain again),while it isn't in optimization locally.Based on the division of adjacent vertices set and different sequence technique, it proposes a new algorithm: cut branch and bound. This method has strong points of the branch and bound: it deletes the unvalued point in process of searching MCP, decomposes random graph with the theory of division of adjacent vertices set, which reduces the domain on MCP's solution and quicken the convergence of this algorithms, searches the clique finally. Different techniques are applied to different graphs on MCP searching: for dense graph MCP, greedy search is the best, because of high probability at the maximum degree vertex; for sparse graph MCP, Non-greedy search is the best, because of high probability at the minimum degree vertex; for medium graph MCP, with regard to high probability at the average vertex, average degree search, proposed under my tutor's guidance, is the best, which quickens up searching speed. Having applied to random graph, fine results have been achieved.It is worth much attention on how to decompose G effectively while studying the problem of NP-C. It is just my original intention and emphasis in the further research. |
