Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time

DOI10.1007/978-3-540-75142-7_16zbMath1145.68588OpenAlexW2162831161MaRDI QIDQ3523207

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

graph spannerstime complexitydistributed algorithms

Mathematics Subject Classification ID

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

Related Items (10)

Derandomizing local distributed algorithms under bandwidth restrictions ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ 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

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