A Solution to Graph Coloring Problem Using Genetic Algorithm
ICST Transactions on Scalable Information Systems · 15.03.2024
DOI: 10.4108/eetsis.5437 ↗Kurz gefasst
Fachartikel in der Zeitschrift ICST Transactions on Scalable Information Systems, online erschienen am 15.03.2024. Verfasst von Karan Malhotra und 4 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 16 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-SA 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Malhotra, K., Vasa, K. D., Chaudhary, N., Vishnoi, A., & Sapra, V. (2024). A Solution to Graph Coloring Problem Using Genetic Algorithm. ICST Transactions on Scalable Information Systems. https://doi.org/10.4108/eetsis.5437
Vancouver
Malhotra K, Vasa KD, Chaudhary N, Vishnoi A, Sapra V. A Solution to Graph Coloring Problem Using Genetic Algorithm. ICST Transactions on Scalable Information Systems. 2024. doi:10.4108/eetsis.5437
BibTeX
@article{Malhotra2024,
author = {Malhotra, Karan and Vasa, Karan D and Chaudhary, Neha and Vishnoi, Ankit and Sapra, Varun},
title = {A Solution to Graph Coloring Problem Using Genetic Algorithm},
journal = {ICST Transactions on Scalable Information Systems},
year = {2024},
doi = {10.4108/eetsis.5437}
}
EUVIMED