Research On Heuristic Algorithm For Graph Coloring Problem

The graph coloring problem (GCP) is a widely studied combinatorial optimization problem .It is a fundamental problem in scientific computation and engineering design. In fact, several classes of real life problems such as examination timetabling and frequency assignment can be modeled as GCP extensions, Yet, it cannot be expected that an algorithm can find, in polynomial time, a solution to an arbitrary GCP instance, because the GCP is NP-hard.The fast and effective approximate algorithms are needed to solve the large scale problem in reasonable computing time. The known approximate algorithm can not give a good enough solution for larger instance in reasonable time. So ILS based Relation of local optimal and global coloring (ILSBR) and a multilevel reduction algorithm to GCP are proposed. They are based on the analysis of the relation of local optimal and global optimal coloring of the GCP finding that the partial solution of the global optimal solution is obtained by a very high probability through intersecting the local optimal solutions. Using the partial solution could construct a kind of perturbation strategy (RLG Re-coloring) which then is applied to Iterated Local Search. And multilevel reduction algorithm reduces the size of the solution with the partial solution.The experimental results on DIMACS benchmark show that the ILS outperforms the known best ones in the running time without decrease in the quality of solutions.