Solving Graph Coloring Problem Using Genetic Algorithm

Authors

  • A. Nivetha  MSc Mathematics, Dr SNS Rajalakshmi College of Arts and Science, Coimbatore, Tamil Nadu, India
  • T. Ramesh  Assistant Professor, Dr SNS Rajalakshmi College of Arts and Science, Coimbatore, Tamil Nadu, India

DOI:

https://doi.org/10.32628/18410IJSRSET

Keywords:

Genetic Algorithm, Binary Coding, Graph Coloring.

Abstract

To Solve the Graph Coloring Problem we use the Genetic Algorithm (GA) that uses the classical crossover operation .Graph Coloring Problem is the interest researcher's area. We use the chromosomes as a binary operators. By Evolutionary Algorithm (EA) of Coloring is an assignment of colors to the vertices of a graph ‘G’ such that no two Adjacent Vertices have the same color. We reduce the chromatic number (maximum out degree +1) using the Genetic Algorithm till get the optimum solution.

References

  1. M. Kubale , "Graph colorings," American Mathematical Society, 2004.
  2. C. W. K. Chen and D. Y. Y. Yun, "Unifying graph-matching problem with a practical solution," in Proc. International Conf. on Systems, Signals, Control, Computers, September 1998.
  3. B. H. Gwee, M. H. Lim, and J. S. Ho, "Solving four-coloring map problem using genetic algorithm," in Proc. Artificial Neural Networks and Expert Systems.
  4. B. Ray, A. J. Pal, D. Bhattacharyya, and T. Kim, "An efficient GA with multipoint guided mutation for graph coloring problems," International Journal of Signal Processing, Image Processing and Pattern Recognition, vol. 3, no. 2, pp. 51-58, 2010.
  5. A. Lim, Y. Zhu, Q. Lou, and B. Rodrigues, "Heuristic methods for graph coloring problems," in Proc. Symposium on Applied Computing, 2005.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2018-09-30

Issue

Volume 4, Issue 10, September-October-2018

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
A. Nivetha, T. Ramesh "Solving Graph Coloring Problem Using Genetic Algorithm" International Journal of Scientific Research in Science, Engineering and Technology (IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 4, Issue 10, pp.202-205, September-October-2018. Available at doi : https://doi.org/10.32628/18410IJSRSET