Article Per Year (5 Year)
p-Index From 2021 - 2026
0.61
P-Index
This Author published in this journals
All Journal International Journal of Electrical and Computer Engineering
Velin Kralev
South-West University “Neofit Rilski”
Computer Science & IT Electrical & Electronics Engineering

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

Found 3 Documents
Search

 1 
An analysis between exact and approximate algorithms for the k-center problem in graphs Velin Kralev; Radoslava Kraleva; Viktor Ankov; Dimitar Chakalov
International Journal of Electrical and Computer Engineering (IJECE) Vol 12, No 2: April 2022
Publisher : Institute of Advanced Engineering and Science

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.11591/ijece.v12i2.pp2058-2065

Abstract

This research focuses on the k-center problem and its applications. Different methods for solving this problem are analyzed. The implementations of an exact algorithm and of an approximate algorithm are presented. The source code and the computation complexity of these algorithms are presented and analyzed. The multitasking mode of the operating system is taken into account considering the execution time of the algorithms. The results show that the approximate algorithm finds solutions that are not worse than two times optimal. In some case these solutions are very close to the optimal solutions, but this is true only for graphs with a smaller number of nodes. As the number of nodes in the graph increases (respectively the number of edges increases), the approximate solutions deviate from the optimal ones, but remain acceptable. These results give reason to conclude that for graphs with a small number of nodes the approximate algorithm finds comparable solutions with those founds by the exact algorithm.
A comparative analysis between two heuristic algorithms for the graph vertex coloring problem Velin Kralev; Radoslava Kraleva
International Journal of Electrical and Computer Engineering (IJECE) Vol 13, No 3: June 2023
Publisher : Institute of Advanced Engineering and Science

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.11591/ijece.v13i3.pp2981-2989

Abstract

This study focuses on two heuristic algorithms for the graph vertex coloring problem: the sequential (greedy) coloring algorithm (SCA) and the Welsh–Powell algorithm (WPA). The code of the algorithms is presented and discussed. The methodology and conditions of the experiments are presented. The execution time of the algorithms was calculated as the average of four different starts of the algorithms for all analyzed graphs, taking into consideration the multitasking mode of the operating system. In the graphs with less than 600 vertices, in 90% of cases, both algorithms generated the same solutions. In only 10% of cases, the WPA algorithm generates better solutions. However, in the graphs with more than 1,000 vertices, in 35% of cases, the WPA algorithm generates better solutions. The results show that the difference in the execution time of the algorithms for all graphs is acceptable, but the quality of the solutions generated by the WPA algorithm in more than 20% of cases is better compared to the SC algorithm. The results also show that the quality of the solutions is not related to the number of iterations performed by the algorithms.
An analysis between different algorithms for the graph vertex coloring problem Velin Kralev; Radoslava Kraleva
International Journal of Electrical and Computer Engineering (IJECE) Vol 13, No 3: June 2023
Publisher : Institute of Advanced Engineering and Science

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.11591/ijece.v13i3.pp2972-2980

Abstract

This research focuses on an analysis of different algorithms for the graph vertex coloring problem. Some approaches to solving the problem are discussed. Moreover, some studies for the problem and several methods for its solution are analyzed as well. An exact algorithm (using the backtracking method) is presented. The complexity analysis of the algorithm is discussed. Determining the average execution time of the exact algorithm is consistent with the multitasking mode of the operating system. This algorithm generates optimal solutions for all studied graphs. In addition, two heuristic algorithms for solving the graph vertex coloring problem are used as well. The results show that the exact algorithm can be used to solve the graph vertex coloring problem for small graphs with 30-35 vertices. For half of the graphs, all three algorithms have found the optimal solutions. The suboptimal solutions generated by the approximate algorithms are identical in terms of the number of colors needed to color the corresponding graphs. The results show that the linear increase in the number of vertices and edges of the analyzed graphs causes a linear increase in the number of colors needed to color these graphs.
Co-Authors Dimitar Chakalov Radoslava Kraleva Viktor Ankov