A variant of the greedy spanner
Michiel Smid
Carleton University
I will present a recent (in fact, from this week) result by Gali Bar-On and Paz Carmi: A variant of the greedy spanner that has the same theoretical properties as the greedy spanner itself. The worst-case running time of this new algorithm is $O(n^2 \log n)$, which is the same as the best-known time bound for computing the greedy spanner. The advantage of the new algorithm is that it is very simple and only $O(n)$ shortest-path computations are needed.