University of Tehran Journal of Algorithms and Computation 2476-2776 53 1 2021 06 01 $alpha$-Gap Greedy Spanner 41 60 81307 EN Hosein Salami Department of Computer Engineering, Ferdowsi University of Mashhad Mostafa Nouri Baygi Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran Journal Article 2021 05 14 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.<br />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. <br />%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. <br />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. https://jac.ut.ac.ir/article_81307_669c0a0df2c0484e4332a6e5ff9041b6.pdf