Journal of Computer and Knowledge Engineering, Year (2023-1)

Title : ( Improving Greedy Spanner Construction Algorithm )

Authors: hosein salami , Mostafa Nouri Baygi ,

Citation: BibTeX | EndNote

Abstract

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.

Keywords

, computational geometry, greedy spanner, construction algorithm
برای دانلود از شناسه و رمز عبور پرتال پویا استفاده کنید.

@article{paperid:1097245,
author = {Salami, Hosein and Nouri Baygi, Mostafa},
title = {Improving Greedy Spanner Construction Algorithm},
journal = {Journal of Computer and Knowledge Engineering},
year = {2023},
month = {January},
issn = {2538-5453},
keywords = {computational geometry; greedy spanner; construction algorithm},
}

[Download]

%0 Journal Article
%T Improving Greedy Spanner Construction Algorithm
%A Salami, Hosein
%A Nouri Baygi, Mostafa
%J Journal of Computer and Knowledge Engineering
%@ 2538-5453
%D 2023

[Download]