Michael Elkin

Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates

2022 · arXiv (Cornell University)

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 $\textrm{polylog}(n)$ rounds in weighted …