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{sup}2) edges, have a running time Ω(n{sup}ε) for some constant ε > 0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of o(n{sup}2) edges in o(n{sup}ε) time for any constant ε > 0. More precisely, in Linial's free model a.k.a LOCAL model, we construct in n{sup}(O(log_n){sup}(1/2))) time, for every graph, a (3,2)-spanner of O(n{sup}(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 (α{sub}k, β{sub}k) -spanners with O(n{sup}(1+1/k) log_k) edges for every integer parameter k ≥ 1, where α{sub}k+β{sub}k = O(k{sup}(log2_5). If the minimum degree of the graph is Ω(n{sup}(1/2)), then, in the same time complexity, a (5,4)-spanner with O(n) edges can be constructed.