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

DOI10.1145/1281100.1281128MaRDI QIDQ5401411zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Fully dynamic randomized algorithms for graph spanners
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• Dynamic Algorithms for Graph Spanners
• Fast Deterministic Distributed Algorithms for Sparse Spanners

Cited in

(15)

• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
• Optimal maintenance of a spanning tree
• Multipath spanners via fault-tolerant spanners
• Derandomizing local distributed algorithms under bandwidth restrictions
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Distributed spanner approximation
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Temporal cliques admit sparse spanners
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Compact routing messages in self-healing trees
• Distributed Spanner Approximation
• A fast network-decomposition algorithm and its applications to constant-time distributed computation (extended abstract)
• Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
• Temporal cliques admit sparse spanners

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

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