Ultra-Sparse Near-Additive Emulators

DOI10.1145/3465084.3467926MaRDI QIDQ6201954zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Shaked Matar

Publication date 26 March 2024

Published in Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.01036

zbMATH Keywords

distributed algorithmsdeterministicemulators

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: Near-additive (aka $$-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings. Known constructions of near-additive emulators enable one to trade between their sparsity (i.e., number of edges) and the additive stretch $$. Specifically, for any pair of parameters $epsilon>0$, $kappa=1,2,dots$, one can have a $$-emulator with $O(n^{1+1/kappa})$ edges, with $$. At their sparsest, these emulators employ $ccdotn$ edges, for some constant $cgeq2$. We tighten this bound, and show that in fact precisely $n^{1+1/kappa}$ edges suffice. In particular, our emulators can be emph{ultra-sparse}, i.e., we can have an emulator with $n+o(n)$ edges and $$. We also devise a distributed deterministic algorithm in the CONGEST model that builds these emulators in low polynomial time (i.e., in $O(n^{h}o)$ time, for an arbitrarily small constant parameter $ho>0$). Finally, we also improve the state-of-the-art distributed deterministic congest-model construction of $$-spanners devised in the PODC'19 paper [ElkinM19]. Specifically, the spanners of [ElkinM19] have $$ edges, i.e., at their sparsest they employ $Oleft(fracloglognepsilonight{)}^{loglogn}cdotn$ edges. In this paper, we devise an efficient distributed deterministic CONGEST-model algorithm that builds such spanners with $O(n^{1+1/kappa})$ edges for $kappa=Oleft(fraclognlo{g}^{(3)}night)$. At their sparsest, these spanners employ only $O(ncdotloglogn)$ edges.

Cited in

(1)

• Massively parallel algorithms for approximate shortest paths

This page was built for publication: Ultra-Sparse Near-Additive Emulators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201954)