2017/08/03 by Ofer Grossman, Grossman, Ofer, Merav Parter +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1708.01011
openalex publication_date 2017/08/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model). The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al. '10, which computes an optimal-sized (2k-1)-spanner but uses O(n1-1/k) rounds. In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V, E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k ⋅ n1+1/k) edges within O(2k ⋅ n1/2 - 1/k) rounds for every even k. For odd k, the number of rounds is O(2k ⋅ n1/2 - 1/(2k)). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n3/2) edges that uses O(log n)-size messages and \widetildeO(1) rounds. If the nodes have IDs in [1, Θ(n)], then the algorithm works in only 2 rounds!