Journal of Algorithms and Computation, Volume (53), No (1), Year (2021-6) , Pages (41-60)

Title : ( $\alpha$-Gap Greedy Spanner )

Authors: hosein salami , Mostafa Nouri Baygi ,

Citation: BibTeX | EndNote


In this paper, we have introduced a new geometric spanner called α-Gap greedy spanner, which is a parametric approximation of the well-known Gap-greedy spanner. We will show theoretically and experimentally that this spanner is similar to the Gap-greedy spanner in terms of qualitative features such as weight and maximum degree of vertices. %Wehave shown that this spanner can be computed in O(n2logn) time withO(n) space, and O(nlogn) expected time on the set of points placedrandomly in a unit square. Two algorithms have been proposed with running time O(n2logn) for constructing the α-Gap greedy spanner. Space complexity of the first algorithm is O(n2), but it is reduced to O(n) in the second one. %The proposed algorithms have a parameter, called α, by which the similarity of the α-Gap greedy spanner to the Gap-greedy spanner, in terms of quality features mentioned above, can be determined. Also, we have shown on the points placed randomly in a unit square, the α-Gap greedy spanner can be constructed in the expected O(nlogn) time.


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

author = {Salami, Hosein and Nouri Baygi, Mostafa},
title = {$\alpha$-Gap Greedy Spanner},
journal = {Journal of Algorithms and Computation},
year = {2021},
volume = {53},
number = {1},
month = {June},
issn = {2476-2776},
pages = {41--60},
numpages = {19},
keywords = {computational geometry; geometric spanners; gap greedy spanner; construction algorithms; algorithm complexity},


%0 Journal Article
%T $\alpha$-Gap Greedy Spanner
%A Salami, Hosein
%A Nouri Baygi, Mostafa
%J Journal of Algorithms and Computation
%@ 2476-2776
%D 2021