Fast Deterministic Distributed Algorithms for Sparse Spanners

DOI10.1007/11780823_9MaRDI QIDQ3613647zbMATH OpenOpenAlexFDO

Authors Bilel Derbel, Cyril Gavoille

Publication date 12 March 2009

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11780823_9

zbMATH Keywords

distributed algorithmsdeterministic algorithmstime complexitygraph spannersLinial's free model

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

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

Cited in

(19)

• A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
• Sparser: A Paradigm for Running Distributed Algorithms
• Fast deterministic distributed algorithms for sparse spanners
• Improved deterministic distributed construction of spanners
• Derandomizing local distributed algorithms under bandwidth restrictions
• Congested clique algorithms for graph spanners
• Distributed spanner approximation
• Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Distributed algorithms for low stretch spanning trees
• Simple distributed spanners in dense congest networks
• Efficient algorithms for constructing very sparse spanners and emulators
• Efficient algorithms for constructing very sparse spanners and emulators
• Sublinear fully distributed partition with applications
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• On the locality of distributed sparse spanner construction
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Local Maps: New Insights into Mobile Agent Algorithms
• Distributed Spanner Approximation

This page was built for publication: Fast Deterministic Distributed Algorithms for Sparse Spanners

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