تعداد نشریات | 49 |
تعداد شمارهها | 1,846 |
تعداد مقالات | 19,518 |
تعداد مشاهده مقاله | 9,310,370 |
تعداد دریافت فایل اصل مقاله | 6,542,947 |
Improving Greedy Spanner Construction Algorithm | ||
Computer and Knowledge Engineering | ||
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 08 بهمن 1401 اصل مقاله (1.47 M) | ||
نوع مقاله: Original Article | ||
شناسه دیجیتال (DOI): 10.22067/cke.2023.73447.1033 | ||
نویسندگان | ||
hosein salami؛ Mostafa Nouri Baygi* | ||
Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran. | ||
چکیده | ||
In recent years, several algorithms with different time complexities have been proposed for the construction of greedy spanners. However, a not so apparently suitable algorithm with running time complexity , namely the FG algorithm, is proved to be practically the fastest algorithm known for this task. One of the common bottlenecks in the greedy spanner construction algorithms is their use of the shortest path search operation (usually using Dijkstra’s algorithm). In this paper, we propose some improvements to the FG algorithm in order to reduce the imposed costs of the shortest path search operation, and therefore to reduce the time required for the construction of greedy spanners. In the first improvement, we reduce the number of this operation calls and in the second one, we reduce the cost of each run of the operation. Experimental results show these improvements are able to significantly accelerate the construction of greedy spanners, compared to the other existing algorithms, especially when the stretch factor gets close to 1. | ||
کلیدواژهها | ||
computational geometry؛ greedy spanner؛ construction algorithm | ||
مراجع | ||
| ||
آمار تعداد مشاهده مقاله: 49 تعداد دریافت فایل اصل مقاله: 18 |