On the locality of distributed sparse spanner construction

DOI10.1145/1400751.1400788zbMath1301.68252OpenAlexW2037793233MaRDI QIDQ2934351

Cyril Gavoille, Laurent Viennot, Bilel Derbel, David Peleg

Publication date: 12 December 2014

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

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

zbMATH Keywords

graph spannerstime complexitydistributed algorithms

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (17)

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 ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Distributed distance computation and routing with small messages ⋮ Rumor Spreading with No Dependence on Conductance ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Sublinear fully distributed partition with applications ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Distributed algorithms for ultrasparse spanners and linear size skeletons ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Distributed Spanner Approximation

This page was built for publication: On the locality of distributed sparse spanner construction