Near-linear lower bounds for distributed distance computations, even in sparse networks
From MaRDI portal
Publication:1660917
DOI10.1007/978-3-662-53426-7_3zbMath1393.68129arXiv1605.05109OpenAlexW2964031269MaRDI QIDQ1660917
Amir Abboud, Keren Censor-Hillel, Seri Khoury
Publication date: 16 August 2018
Full work available at URL: https://arxiv.org/abs/1605.05109
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (14)
Distributed Testing of Distance-k Colorings ⋮ Communication costs in a geometric communication network ⋮ Distributed distance computation and routing with small messages ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ A note on hardness of diameter approximation ⋮ Low-congestion shortcut and graph parameters ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Approximate proof-labeling schemes ⋮ Message lower bounds via efficient network synchronization ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Fast approximate shortest paths in the congested clique ⋮ Distributed Spanner Approximation ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
This page was built for publication: Near-linear lower bounds for distributed distance computations, even in sparse networks
