On the locality of distributed sparse spanner construction

DOI10.1145/1400751.1400788MaRDI QIDQ2934351zbMATH OpenOpenAlexFDO

Authors Bilel Derbel, Cyril Gavoille, Laurent Viennot, 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

distributed algorithmsgraph spannerstime complexity

Mathematics Subject Classification ID

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

Recommendations

• Fast deterministic distributed algorithms for sparse spanners
• Local Computation of Nearly Additive Spanners
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Improved deterministic distributed construction of spanners

Cited in

(35)

• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Sublinear fully distributed partition with applications
• Graph spanners: a tutorial review
• Derandomizing local distributed algorithms under bandwidth restrictions
• The sparsest additive spanner via multiple weighted BFS trees
• Distributed construction of low-interference spanners
• Distributed distance computation and routing with small messages
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Rumor spreading with no dependence on conductance
• Simple distributed spanners in dense congest networks
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Local Computation of Nearly Additive Spanners
• Sparser: A Paradigm for Running Distributed Algorithms
• Efficient algorithms for constructing very sparse spanners and emulators
• Efficient algorithms for constructing very sparse spanners and emulators
• Distributed spanner approximation
• scientific article; zbMATH DE number 7376014 (Why is no real title available?)
• Local computation algorithms for spanners
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Congested clique algorithms for graph spanners
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Message Reduction in the LOCAL Model is a Free Lunch
• Near-additive spanners in low polynomial deterministic CONGEST time
• Local approximation schemes for topology control
• Average size of unstretched remote-spanners
• Distributed Spanner Approximation
• Graph spanners in the message-passing model
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Improved deterministic distributed construction of spanners
• Distributed algorithms for low stretch spanning trees
• Constant-round spanners and shortest paths in congested clique and MPC
• Fast deterministic distributed algorithms for sparse spanners

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

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