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.
|Título de la publicación alojada||2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021|
|Editores||Carlos E. Velasquez-Villada|
|Editorial||Institute of Electrical and Electronics Engineers Inc.|
|ISBN (versión digital)||9781665442718|
|Estado||Publicada - 26 may. 2021|
|Evento||2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021 - Virtual, Online|
Duración: 26 may. 2021 → 28 may. 2021
Serie de la publicación
|Nombre||2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021|
|Conferencia||2021 IEEE Colombian Conference on Communications and Computing, COLCOM 2021|
|Período||26/05/21 → 28/05/21|
Nota bibliográficaPublisher Copyright:
© 2021 IEEE.