Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time

DOI10.1007/978-3-540-75142-7_16MaRDI QIDQ3523207zbMATH OpenOpenAlexFDO

Authors Bilel Derbel, Cyril Gavoille, David Peleg

Publication date 2 September 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-75142-7_16

zbMATH Keywords

distributed algorithmstime complexitygraph spanners

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Fast Deterministic Distributed Algorithms for Sparse Spanners
• Fast deterministic distributed algorithms for sparse spanners
• On the locality of distributed sparse spanner construction
• Improved deterministic distributed construction of spanners
• Local Computation of Nearly Additive Spanners

Cited in

(16)

• Graph spanners: a tutorial review
• Fast deterministic distributed algorithms for sparse spanners
• 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
• Near-additive spanners in low polynomial deterministic CONGEST time
• Derandomizing distributed algorithms with small messages: spanners and dominating set
• Distributed algorithms for low stretch spanning trees
• The sparsest additive spanner via multiple weighted BFS trees
• Sublinear fully distributed partition with applications
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• 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 computation algorithms for spanners

This page was built for publication: Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time

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