A METHOD FOR THE GRAPH COLORING PROBLEM USING GENETIC ALGORITHM AND HEURISTIC

摘要：

Graph coloring is a typical NP-Complete problem.This paper puts forward a new method of vertex coloring of a graph based on genetic algorithm and heuristics algorithm.This algorithm involves Chromosomal Representation, Fitness function,selection operator,crossover operator,etc. The algorithm has been implemented and tested on various sets of instances.The experiments show that this new algorithm can improve time complexity and obtain a better result.

关键词： Graph Coloring Genetic Algorithm Heuristics Algorithm Time Complezity

作者: Huichuan Liao

作者单位: School of Information Engineering,East China Jiaotong University Nanchang 330013,P.R.China

会议类型: 国际会议

会议名称: 2009 International Symposium on Computer Science and Technology(2009 中国宁波国际计算机科学与技术学术大会)

会议地点: 宁波

会议语种:英文

页码: 629-632

在线出版日期: 2009-11-20（万方平台首次上网日期，不代表论文的发表时间）