An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs
Abstract
In this research an analysis between the Welsh-Powell and DSatur algorithms for the graph vertex coloring problem was presented. Both algorithms were implemented and analyzed as well. The method of the experiment was discussed and the 46 test graphs, which were divided into two sets, were presented. The results show that for sparse graphs with a smaller number of vertices and edges, both algorithms can be used for solving the problem. The results show that in 50% of the cases the Welsh-Powell algorithm found better solutions (23 in total). So, the DSatur algorithm found better solutions in only 19.6% of cases (9 in total). In the remaining 30.4% of cases, both algorithms found identical solutions. For graphs with a larger number of vertices, the usage of the Welsh-Powell algorithm is recommended as it finds better solutions. The execution time of the DSatur algorithm is greater than the execution time of the Welsh-Powell algorithm, reaching up to a minute for graphs with a larger number of vertices. For graphs with fewer vertices and edges, the execution times of both algorithms are shorter, but the time is still greater for the DSatur algorithm.
Keywords
Chromatic number; Graph coloring; Graph theory; Heuristic algorithm; Vertex coloring
Full Text:
PDFDOI: http://doi.org/10.11591/ijece.v15i4.pp3867-3875
Copyright (c) 2025 Radoslava Kraleva, Velin Kralev, Toma Katsarski
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
International Journal of Electrical and Computer Engineering (IJECE)
p-ISSN 2088-8708, e-ISSN 2722-2578
This journal is published by the Institute of Advanced Engineering and Science (IAES).