A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
From MaRDI portal
Publication:5361854
DOI10.1145/2897518.2897638zbMath1375.68218arXiv1504.07056OpenAlexW2952490263MaRDI QIDQ5361854
Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger
Publication date: 29 September 2017
Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.07056
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (17)
Thorup-Zwick emulators are universally optimal hopsets ⋮ Fast Distributed Approximation for Max-Cut ⋮ Single-source shortest paths in the CONGEST model with improved bounds ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Distributed distance computation and routing with small messages ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Fast approximate shortest paths in the congested clique ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
This page was built for publication: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths