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.
Salami, H. & Nouri Baygi, M. (2021). $\alpha$-Gap Greedy Spanner. Journal of Algorithms and Computation, 53(1), 41-60. https://doi.org/10.22059/jac.2021.81307
MLA
Salami, H., & Nouri Baygi, M. "$\alpha$-Gap Greedy Spanner", Journal of Algorithms and Computation, 53, 1, 2021, 41-60. doi: 10.22059/jac.2021.81307
HARVARD
Salami H., Nouri Baygi M. (2021). '$\alpha$-Gap Greedy Spanner', Journal of Algorithms and Computation, 53(1), pp. 41-60. doi: 10.22059/jac.2021.81307
CHICAGO
H. Salami & M. Nouri Baygi, "$\alpha$-Gap Greedy Spanner," Journal of Algorithms and Computation, 53 1 (2021): 41-60, doi: 10.22059/jac.2021.81307
VANCOUVER
Salami H., Nouri Baygi M. $\alpha$-Gap Greedy Spanner. J. Algo. Comp. 2021;53(1):41-60. doi: 10.22059/jac.2021.81307
