A Method for the Minimum Coloring Problem using Genetic Algorithms

H. Harmanani and H. Abas (Lebanon)


Genetic algorithms, combinatorial opti mization, graph coloring.


This paper presents a method to solve the graph coloring problem for arbitrary graphs using genetic algorithms. The graph coloring problem, an NP-hard problem, has important applications in many areas including time tabling and scheduling, frequency assignment, and reg ister allocation. The algorithm was implemented and tested on various set of instances including large DIMACS challenge benchmark graphs, all yielding favorable results.

Important Links:

Go Back