Improving Greedy Spanner Construction Algorithm

Computer and Knowledge Engineering

دوره 6، شماره 1 - شماره پیاپی 11، تیر 2023، صفحه 27-35   

نوع مقاله: 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

مراجع