An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs.
Saved in:
| Title: | An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs. |
|---|---|
| Authors: | Kraleva, Radoslava1 rady_kraleva@swu.bg, Kralev, Velin1 velin_kralev@swu.bg, Katsarski, Toma1 t.katsarski@swu.bg |
| Source: | International Journal of Electrical & Computer Engineering (2088-8708). Aug2025, Vol. 15 Issue 4, p3867-3875. 9p. |
| Subjects: | Graph coloring, Sparse graphs, Algorithms, Time complexity |
| 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. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Electrical & Computer Engineering (2088-8708) is the property of Institute of Advanced Engineering & Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
