Message Optimality and Message-Time Trade-offs for APSP and Beyond
Open Access
- 13 June 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 299-309
Abstract
No abstract availableAll Related Versions
Funding Information
- NSF (National Science Foundation) (CCF-2402835, CCF-2402836, CCF-2402837)
- Army Research Office (W911NF-231-0191)
This publication has 22 references indexed in Scilit:
- Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n^{5/4}) Rounds2017
- Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks2016
- Near-Optimal Scheduling of Distributed Algorithms2015
- On the Complexity of Universal Leader ElectionJournal of the ACM, 2015
- On the power of the congested clique model2014
- Parallel graph decompositions using random shifts2013
- Networks Cannot Compute Their Diameter in Sublinear Time2012
- Distributed Computing: A Locality-Sensitive Approach2000
- Packet routing and job-shop scheduling inO(congestion+dilation) stepsCombinatorica, 1994
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986