High-efficient Incomplete Search Method On Graph Coloring Problem

Graph coloring problem is a typical NP problem, the current method of solving the Graph coloring problem can be divided into the complete search method and the incomplete search method. The complete search method is used for searching all the possible space of the problem to find the solution in a certain sequence, the incomplete search method is used to search the most effective space for finding the solution of the Graph coloring problem. For the high efficient of the incomplete algorithm, it is widely used .The key point of graph coloring problem research is to find the suitable node coloring in a reasonable way. This paper transforms the graph coloring problem to Boolean satisfiability problem, using the measures and the concepts which used in the Boolean satisfiability for the graph coloring problem, make it into a numerical problem.In the process of solving the graph coloring problem, this paper finding out the complete subgraph of the graph, then coloring the complete subgraph in a certain way and searching the solution of the problem in the remaining graph. This measure makes the searching space smaller and reducing the burden of the algorithm on search .Meanwhile the algorithm using the promising decreasing variable which defined in the Boolean satisfiability problem to solve the graph coloring problem. By defining the promising decreasing variable in this problem, it accelerated the speed of algorithm to find the solution. This algorithm using the union strategy which is combined of the second best strategy and the noise strategy, it enhances the ability of the algorithm, make searching in the complex structure easier.This method of searching on graph coloring problem has good results in DIMACS, especially for DSJC. It can get the best records in the most examples. This algorithm performs better in the graph which has large scale complete subgraph.