EUVIMEDSkopri EUVIMED
Open access · CC BY-NC-SA 4.0

A Solution to Graph Coloring Problem Using Genetic Algorithm

Karan Malhotra, Karan D Vasa, Neha Chaudhary, Ankit Vishnoi, Varun Sapra

ICST Transactions on Scalable Information Systems · 2024-03-15

DOI: 10.4108/eetsis.5437 ↗

At a glance

Journal article in ICST Transactions on Scalable Information Systems, published online on 2024-03-15. Written by Karan Malhotra and 4 co-authors. Cited 3 times so far (Crossref); 16 references. The full text is freely available (open access, CC BY-NC-SA 4.0).

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →