Fast deterministic distributed algorithms for sparse spanners

AbstractThis 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(n2) edges, have a running time Ω(nϵ) for some constant ϵ>0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n2) edges in o(nϵ) time for any constant ϵ>0.More precisely, in Linial’s free model a.k.a LOCAL model, we construct in nO(1/logn) time, for every graph, a (3,2)-spanner of O(n3/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 (αk,βk)-spanners with O(n1+1/klogk) edges for every integer parameter k≥1, where αk+βk=O(klog25). If the minimum degree of the graph is Ω(n), then, in the same time complexity, a (5,4)-spanner with O(n) edges can be constructed