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

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

Resumen

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.

Idioma originalInglés
Título de la publicación alojada2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021
EditoresCarlos E. Velasquez-Villada
EditorialInstitute of Electrical and Electronics Engineers Inc.
ISBN (versión digital)9781665442718
DOI
EstadoPublicada - 26 may. 2021
Evento2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021 - Virtual, Online
Duración: 26 may. 202128 may. 2021

Serie de la publicación

Nombre2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021

Conferencia

Conferencia2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021
CiudadVirtual, Online
Período26/05/2128/05/21

Nota bibliográfica

Publisher Copyright:
© 2021 IEEE.

Huella

Profundice en los temas de investigación de 'Comparative Analysis of the main Graph Coloring Algorithms'. En conjunto forman una huella única.

Citar esto