Comparative Analysis of the main Graph Coloring Algorithms

Juan Postigo, Juan Soto-Begazo, Villarroel R. Fiorela, Gleddynuri M. Picha, Roxana Flores-Quispe, Yuber Velazco-Paredes

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The graph coloring problem, GCP, beyond theoretical interest, it has significant practical importance due to the frequent real-life situations in which problems arise that can be modeled as a graph coloring problem. In this research, algorithms dedicated to solving the Graph Coloring Problem such as Greedy, Dsatur, RLF, AntCOL and TabuCol are described, making an objective comparison between them, reviewing parameters such as the computational time used by these, the memory of quantities and its performance as a function of the number of vertices and edges. The experimental results show that the most efficient algorithms in speed are the Greedy and dsatur. On the other hand, the tabucol and AntCol algorithms show a notable difference of inefficiency compared to large graphs, finding very good solutions, in addition, although the RLF algorithm is generally memory deficient, it presents solutions with high quality. Consequently, certain applications benefited by these algorithms are known.

Original languageEnglish
Title of host publication2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021
EditorsCarlos E. Velasquez-Villada
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781665442718
DOIs
StatePublished - 26 May 2021
Event2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021 - Virtual, Online
Duration: 26 May 202128 May 2021

Publication series

Name2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021

Conference

Conference2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021
CityVirtual, Online
Period26/05/2128/05/21

Bibliographical note

Publisher Copyright:
© 2021 IEEE.

Keywords

  • Ant Colony (AntCol)
  • Degree of Saturation
  • Graph coloring
  • Greedy
  • Recursive Largest First
  • TabuCol

Fingerprint

Dive into the research topics of 'Comparative Analysis of the main Graph Coloring Algorithms'. Together they form a unique fingerprint.

Cite this