TY - JOUR
ID - 3608
TI - Greedy Spanner Algorithms in Practice
JO - Scientia Iranica
JA - SCI
LA - en
SN - 1026-3098
AU - Farshi, Mohammad
AU - HekmatNasab, MohammadJavad
AD - Department of Computer Science, Yazd University, P.O. Box 89195-741, Yazd, Iran.
Y1 - 2014
PY - 2014
VL - 21
IS - 6
SP - 2142
EP - 2152
KW - geometric networks
KW - Euclidean graphs
KW - geometric spanners
KW - greedy algorithm
KW - greedy spanner
DO -
N2 - Spanners generated by the greedy algorithm{ or greedy spanners{ not only have good theoretical properties, like a linear number of edges, low degree and low weight, but previous experimental results also show that they are superior to spanners generated by other algorithms in practice. Because of the good properties of greedy spanners, they found several applications like in protein visualization. The major issue in computing greedy spanners is the high time and space complexity of algorithms that compute it. To construct the greedy spanner on a set of n points, the original greedy algorithm takes O(n3 log n) time. In 2005, an improvement was proposed by Farshi and Gudmundsson [Lecture Notes in Computer Science, Vol. 3669, pages 556{567] that works much faster in practice, but later it was shown that it has same theoretical time complexity. In 2008, Bose et al. [Lecture Notes in Computer Science, Vol. 5124, pages 390{401] discovered a near-quadratic time algorithm for constructing greedy spanners. In this paper, we compare time complexity of these three algorithms for computing the greedy spanner in practice.
UR - https://scientiairanica.sharif.edu/article_3608.html
L1 - https://scientiairanica.sharif.edu/article_3608_9c925876e282a3e64c2d602fc901a2c2.pdf
ER -