2026-07-24T17:54:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8008 2024-03-06T10:41:40Z ddc:004 open_access

Improved Deterministic Distributed Construction of Spanners Grossman, Ofer Parter, Merav spanners clustering deterministic algorithms congest model 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., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-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 n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds! Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ofer Grossman and Merav Parter 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.24 urn:nbn:de:0030-drops-80085 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.24 eng https://creativecommons.org/licenses/by/3.0/legalcode