2010-11-01
Computing the greedy spanner in near-quadratic time
Publication
Publication
Algorithmica
,
Volume 58
-
Issue 3
p. 711-
729
The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in O(n 2log n) time. Since computing the greedy spanner has an Ω(n 2) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.
| Additional Metadata | |
|---|---|
| Keywords | Dilation, Doubling dimension, Greedy algorithm, Spanner, Stretch factor |
| Persistent URL | dx.doi.org/10.1007/s00453-009-9293-4 |
| Journal | Algorithmica |
| Citation |
Bose, P, Carmi, P. (Paz), Farshi, M. (Mohammad), Maheshwari, A, & Smid, M. (2010). Computing the greedy spanner in near-quadratic time. Algorithmica, 58(3), 711–729. doi:10.1007/s00453-009-9293-4
|