Fast deterministic distributed algorithms for sparse spanners
This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with n nodes. All previous deterministic distributed algorithms, for constant stretch spanners of o(n(2)) edges, have a running time Omega(n(epsilon)) for some constant epsilon > 0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n(2)) edges in o(n(epsilon)) time for any constant epsilon > 0. More precisely, in Linial's free model a.k.a LOCAL model, we construct in n(O(1/root log n)) time, for every graph, a (3, 2)-spanner of O(n(3/2)) edges, i.e., a spanning subgraph in which the distance is at most 3 times the distance of the original graph plus 2. The result is extended to (alpha(k), beta(k))-spanners with O(n(1+1/k) log k) edges for every integer parameter k >= 1, where alpha(k)+beta(k) = O(k(log25)). If the minimum degree of the graph is Omega(root n), then, in the same time complexity, a (5, 4)-spanner with O (n) edges can be constructed. (C) 2008 Elsevier B.V. All rights reserved.
distributed algorithms linial's free model time complexity graph spanners