A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners

DOI10.1145/1281100.1281128zbMath1283.68396OpenAlexW2077059864MaRDI QIDQ5401411

Michael Elkin

Publication date: 13 March 2014

Published in: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1281100.1281128

zbMATH Keywords

spannersdistributed dynamic algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (11)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Compact routing messages in self-healing trees ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Multipath Spanners via Fault-Tolerant Spanners ⋮ Distributed construction of purely additive spanners ⋮ Temporal cliques admit sparse spanners ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ Temporal Cliques Admit Sparse Spanners ⋮ Distributed Spanner Approximation ⋮ Unnamed Item

This page was built for publication: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners