Deterministic distributed construction of linear stretch spanners in polylogarithmic time

Abstract. The paper presents a deterministic distributed algorithm that given an n node unweighted graph constructs an O(n3/2) edge 3-spanner for it in O(log n) time. This algorithm is then extended into a deterministic algorithm for computing an O(kn1+1/k) edge O(k)-spanner in O(logk−1 n) time for every integer parameter k> 1. This establishes that the problem of the deterministic construction of a low stretch span-ner with few edges can be solved in the distributed setting in polyloga-rithmic time. The paper also investigates the distributed construction of sparse span-ners with almost pure additive stretch (1 + ǫ, β), i.e., such that the dis-tance in the spanner is at most 1 + ǫ times the original distance plus β. It is shown, for every ǫ> 0, that in O(log n/ǫ) time one can de-terministically construct a spanner with O(n3/2) edges that is both a 3-spanner and a (1+ ǫ, 8 log n)-spanner. Furthermore, it is shown that in nO(1/ log n) +O(1/ǫ) time one can deterministically construct a spanner with O(n3/2) edges which is both a 3-spanner and a (1 + ǫ, 4)-spanner. (This algorithm can be transformed into a Las Vegas randomized algo-rithm with guarantees on the stretch and time, running in O(log n+1/ǫ) expected time)