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.05109MaRDI QIDQ1660917
Amir Abboud, Keren Censor-Hillel, Seri Khoury
Publication date: 16 August 2018
Full work available at URL: https://arxiv.org/abs/1605.05109
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Distributed Spanner Approximation, Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time, Distributed Testing of Distance-k Colorings, The Sparsest Additive Spanner via Multiple Weighted BFS Trees, Approximate proof-labeling schemes, Communication costs in a geometric communication network, A note on hardness of diameter approximation, Redundancy in distributed proofs, Fast approximate shortest paths in the congested clique, The sparsest additive spanner via multiple weighted BFS trees, Low-congestion shortcut and graph parameters, Message lower bounds via efficient network synchronization, Distributed distance computation and routing with small messages