Prof. Michael Elkin

In the distributed setting, the only existing constructions of sparse skeletons, (i.e., subgraphs with O(n) edges) either use randomization or large messages, or require Ω(D) time, where D is the hop-diameter of the input graph G. We devise the first deterministic distributed algorithm in the CONGEST model (i.e., uses small messages) for constructing linear-size skeletons in time 2O(√ log n·log log n). We can also compute a linear-size spanner with stretch polylog(n) in low deterministic polynomial time, i.e., O(nρ) for an arbitrarily small constant ρ > 0, in the CONGEST model. Yet another algorithm that we devise runs in O(log n) κ−1time, for a parameter κ = 1, 2, . . . , and constructs an O(log n) κ−1spanner with O(n 1+ 1κ ) edges. All our distributed algorithms are lightweight from the computational perspective, i.e., none of them employs any heavy computations.