@article {
author = {Salami, Hosein and Nouri Baygi, Mostafa},
title = {$\alpha$-Gap Greedy Spanner},
journal = {Journal of Algorithms and Computation},
volume = {53},
number = {1},
pages = {41-60},
year = {2021},
publisher = {University of Tehran},
issn = {2476-2776},
eissn = {2476-2784},
doi = {10.22059/jac.2021.81307},
abstract = {In this paper, we have introduced a new geometric spanner called $\alpha$-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(n^2 \log n)$ time with$O(n)$ space, and $O(n \log n)$ expected time on the set of points placedrandomly in a unit square.Two algorithms have been proposed with running time $O(n^2 \log n)$ for constructing the $\alpha$-Gap greedy spanner. Space complexity of the first algorithm is $O(n^2)$, but it is reduced to $O(n)$ in the second one. %The proposed algorithms have a parameter, called $\alpha$, by which the similarity of the $\alpha$-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 $\alpha$-Gap greedy spanner can be constructed in the expected $O(n \log n)$ time.},
keywords = {computational geometry,geometric spanners,gap greedy spanner,construction algorithms,algorithm complexity},
url = {https://jac.ut.ac.ir/article_81307.html},
eprint = {https://jac.ut.ac.ir/article_81307_669c0a0df2c0484e4332a6e5ff9041b6.pdf}
}