Comparative Analysis of the main Graph Coloring Algorithms

Autor: Villarroel R. Fiorela, Yuber Velazco-Paredes, Roxana Flores-Quispe, Juan Postigo, Juan Soto-Begazo, Gleddynuri M. Picha
Rok vydání: 2021
Předmět:
Zdroj: 2021 IEEE Colombian Conference on Communications and Computing (COLCOM).
DOI: 10.1109/colcom52710.2021.9486299
Popis: 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.
Databáze: OpenAIRE