A Solution to Graph Coloring Problem Using Genetic Algorithm
DOI:
https://doi.org/10.4108/eetsis.5437Keywords:
Genetic Algorithm, Serial execution, parallel execution, graph colouringAbstract
INTRODUCTION: The Graph Coloring Problem (GCP) involves coloring the vertices of a graph in such a way that no two adjacent vertices share the same color while using the minimum number of colors possible.
OBJECTIVES: The main objective of the study is While keeping the constraint that no two neighbouring vertices have the same colour, the goal is to reduce the number of colours needed to colour a graph's vertices. It further investigate how various techniques impact the execution time as the number of nodes in the graph increases.
METHODS: In this paper, we propose a novel method of implementing a Genetic Algorithm (GA) to address the GCP.
RESULTS: When the solution is implemented on a highly specified Google Cloud instance, we likewise see a significant increase in performance. The parallel execution on Google Cloud shows significantly faster execution times than both the serial implementation and the parallel execution on a local workstation. This exemplifies the benefits of cloud computing for computational heavy jobs like GCP.
CONCLUSION: This study illustrates that a promising solution to the Graph Coloring Problem is provided by Genetic Algorithms. Although the GA-based approach does not provide an optimal result, it frequently produces excellent approximations in a reasonable length of time for a variety of real-world situations.
References
Dey, Arindam et al. ‘A Genetic Algorithm for Total Graph Coloring’, Journal of Intelligent & Fuzzy Systems, vol. 37, no. 6, pp. 7831-7838, 2019.
S. Balakrishnan, Tamilarasi Suresh, Raja Marappan. (2021) A New Multi-Objective Evolutionary Approach to Graph Coloring and Channel Allocation Problems. Journal of Applied Mathematics and Computation, 5(4), 252-263.
Ardelean, Sebastian Mihai, and Mihai Udrescu. “Graph coloring using the reduced quantum genetic algorithm.” PeerJ. Computer science vol. 8, e836, Jan. 2022, doi:10.7717/peerj-cs.836.
idi Mohamed Douiri, Souad Elbernoussi, “Solving the graph coloring problem via hybrid genetic algorithms”, Journal of King Saud University - Engineering Sciences, Volume 27, Issue 1, 2015, Pages 114-118, ISSN 1018-3639, https://doi.org/10.1016/j.jksues.2013.04.001.
Marappan, R., Sethumadhavan, G. Solution to Graph Coloring Using Genetic and Tabu Search Procedures. Arab J Sci Eng 43, 525–542 (2018). https://doi.org/10.1007/s13369-017-2686-9.
X. Li, L. Gao, Q. Pan, L. Wan and K. -M. Chao, "An Effective Hybrid Genetic Algorithm and Variable Neighborhood Search for Integrated Process Planning and Scheduling in a Packaging Machine Workshop," in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 49, no. 10, pp. 1933-1945, Oct. 2019, doi: 10.1109/TSMC.2018.2881686.
Hamed Kazemi, Mohammad MahdaviMazdeh, Mohammad Rostami & Mahdi Heydari (2021) The integrated production-distribution scheduling in parallel machine environment by using improved genetic algorithms, Journal of Industrial and Production Engineering, 38:3, 157-170, DOI: 10.1080/21681015.2020.1848930.
Feng Liu, Kan Fang, Jiafu Tang, Yong Yin, “Solving the rotating seru production problem with dynamic multi-objective evolutionary algorithms”, Journal of Management Science and Engineering, Volume 7, Issue 1, 2022, Pages 48-66, ISSN 2096-2320, https://doi.org/10.1016/j.jmse.2021.05.004.
R. Marappan and G. Sethumadhavan, “Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem,” Mathematics, vol. 8, no. 3, p. 303, Feb. 2020, doi: 10.3390/math8030303.
Mohamed, A.W., Hadi, A.A. & Mohamed, A.K. Gaining-sharing knowledge based algorithm for solving optimization problems: a novel nature-inspired algorithm. Int. J. Mach. Learn. & Cyber. 11, 1501–1529 (2020). https://doi.org/10.1007/s13042-019-01053-x.
R. Marappan and G. Sethumadhavan, "A New Genetic Algorithm for Graph Coloring," 2013 Fifth International Conference on Computational Intelligence, Modelling and Simulation, Seoul, Korea (South), 2013, pp. 49-54, doi: 10.1109/CIMSim.2013.17.
Eiben, A., van der Hauw, J. & van Hemert, J. Graph Coloring with Adaptive Evolutionary Algorithms. Journal of Heuristics 4, 25–46 (1998). https://doi.org/10.1023/A:1009638304510.
Eiben, A., van der Hauw, J. & van Hemert, J. Graph Coloring with Adaptive Evolutionary Algorithms. Journal of Heuristics 4, 25–46 (1998). https://doi.org/10.1023/A:1009638304510.
R. Marappan and G. Sethumadhavan, "Solution to graph coloring problem using divide and conquer based genetic method," 2016 International Conference on Information Communication and Embedded Systems (ICICES), Chennai, India, 2016, pp. 1-5, doi: 10.1109/ICICES.2016.7518911.
Kong, Y., Wang, F., Lim, A., Guo, S. (2003). A New Hybrid Genetic Algorithm for the Robust Graph Coloring Problem. In: Gedeon, T. (D., Fung, L.C.C. (eds) AI 2003: Advances in Artificial Intelligence. AI 2003. Lecture Notes in Computer Science(), vol 2903. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24581-0_11.
Brighen, A., Slimani, H., Rezgui, A. et al. A new distributed graph coloring algorithm for large graphs. Cluster Comput (2023). https://doi.org/10.1007/s10586-023-03988-x.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Karan Malhotra, Karan D Vasa, Neha Chaudhary, Ankit Vishnoi, Varun Sapra
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This is an open access article distributed under the terms of the CC BY-NC-SA 4.0, which permits copying, redistributing, remixing, transformation, and building upon the material in any medium so long as the original work is properly cited.
