Near-linear lower bounds for distributed distance computations, even in sparse networks

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

zbMATH Keywords

diameter; approximations; lower bounds; eccentricity; radius; distributed computing; spanners

Mathematics Subject Classification ID

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