A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n^{1+1/k}) Size in Weighted Graphs

a sub-graph $G(V,E_S)$ such that the distance between any pair of vertices
in the spanner is at most $t$ times the distance between the two in the
given
graph. A 1963 girth conjecture of Erdos implies that $\Omega(n^{1+1/k})$
edges
are required in the worst case for any $(2k-1)$-spanner, which
has been proved for $k=1,2,3,5$. There exist polynomial time
algorithms that can construct spanners with the size that matches this
conjectured lower bound, and the best known algorithm takes $O(mn^{1/k})$
expected running time. In this talk, we present an extremely simple
linear time randomized
algorithm that constructs $(2k-1)$-spanner of size matching the
conjectured lower bound.

Our algorithm requires local information for computing a spanner,
and thus can be adapted suitably to obtain efficient distributed and
parallel algorithms.