Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhoň · 2022
This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification:We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in polylog(n) rounds in weighted graphs. Concretely, our algorithm outputs a spanning subgraph with only n + o (n) edges in which the pairwise distances are stretched by a factor of at most O(logn · 2O(log* n) ).