Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal International Journal of Electrical and Computer Engineering
Katsarski, Toma
Unknown Affiliation
Computer Science & IT Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
An analysis between the Welsh-Powell and DSatur algorithms for coloring of sparse graphs Kraleva, Radoslava; Kralev, Velin; Katsarski, Toma
International Journal of Electrical and Computer Engineering (IJECE) Vol 15, No 4: August 2025
Publisher : Institute of Advanced Engineering and Science

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.11591/ijece.v15i4.pp3867-3875

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.
Co-Authors Kralev, Velin Kraleva, Radoslava