Fast Partial Distance Estimation and Applications

DOI10.1145/2767386.2767398zbMath1333.68280arXiv1412.7922OpenAlexW2040273581MaRDI QIDQ2796252

Boaz Patt-Shamir, Christoph Lenzen

Publication date: 23 March 2016

Published in: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.7922

zbMATH Keywords

source detectioncongest modelrouting table constructionSteiner forestsweighted all-pairs shortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Single-source shortest paths in the CONGEST model with improved bounds, Distributed distance computation and routing with small messages, Routing schemes for hybrid communication networks, On efficient distributed construction of near optimal routing schemes, Unnamed Item, Fast approximate shortest paths in the congested clique, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, 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 Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE, Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree, Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

Cites Work

• Memorization and Association on a Realistic Neural Model
• Unnamed Item