journal6 ›› 2008, Vol. 29 ›› Issue (5): 57-60.

• Physics and electronics • Previous Articles     Next Articles

Vertex Coloring of a Graph Based on Genetic and Heuristics Search Algorithm


  1. (School of Information Engineering,East China Jiaotong University,Nanchang 330013,China)
  • Online:2008-09-25 Published:2012-05-20

Abstract: Graph coloring is a typical NP-completely problem.This paper puts forward a new method of vertex coloring of a graph based on genetic algorithm and heuristics search algorithm.This algorithm involves the coding methods of chromosome,the design of fitness function and the selection operators.Experiments show that this new algorithm can improve time complexity and obtain solutions of excellent quality.

Key words: graph coloring;heuristics search algorithm;genetic algorithm, time complexity

WeChat e-book chaoxing Mobile QQ