Parallel Greedy Spanners
share
A t-spanner of a graph is a subgraph that t-approximates pairwise distances. The greedy algorithm is one of the simplest and most well-studied algorithms for constructing a sparse spanner: it computes a t-spanner with n^1+O(1/t) edges by repeatedly choosing any edge which does not close a cycle of chosen edges with t+1 or fewer edges. We demonstrate that the greedy algorithm computes a t-spanner with t^3·log^3 n · n^1 + O(1/t) edges even when a matching of such edges are added in parallel. In particular, it suffices to repeatedly add any matching where each individual edge does not close a cycle with t +1 or fewer edges but where adding the entire matching might. Our analysis makes use of and illustrates the power of new advances in length-constrained expander decompositions.
READ FULL TEXT