Improved Local Computation Algorithms for Constructing Spanners

Rubi Arviv, Lily Chung, Reut Levi +1

A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every $k$, a spanner with size $O(n^{1+1/k})$ and stretch $(2k+1)…