Fast approximate shortest paths in the congested clique
From MaRDI portal
Publication:2064057
DOI10.1007/s00446-020-00380-5MaRDI QIDQ2064057
Michal Dory, Dean Leitersdorf, Keren Censor-Hillel, Janne H. Korhonen
Publication date: 4 January 2022
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-020-00380-5
distributed computing; matrix multiplication; hopsets; all-pairs shortest paths; congested clique model
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Lessons from the congested clique applied to MapReduce
- Thorup-Zwick emulators are universally optimal hopsets
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- Algebraic methods in the congested clique
- Sparse matrix multiplication and triangle listing in the congested clique model
- All-Pairs Small-Stretch Paths
- Fast Partial Distance Estimation and Applications
- Optimal distributed all pairs shortest paths and applications
- On the power of the congested clique model
- Distributed Algorithms for Network Diameter and Girth
- On a routing problem
- Powers of tensors and fast matrix multiplication
- Spanners and emulators with sublinear distance errors
- Faster Approximation of Distances in Graphs
- Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- “Tri, Tri Again”: Finding Triangles and Small Subgraphs in a Distributed Setting
- All-Pairs Almost Shortest Paths
- Distributed exact shortest paths in sublinear time
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- (Delta+1) Coloring in the Congested Clique Model
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- Congested Clique Algorithms for Graph Spanners
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Optimal deterministic routing and sorting on the congested clique
- Efficient distributed source detection with limited bandwidth
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
- Congested Clique Algorithms for the Minimum Cut Problem
- Distributed exact weighted all-pairs shortest paths in near-linear time
- Towards tight approximation bounds for graph diameter and eccentricities
- Improved distributed algorithms for exact shortest paths
- Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
- Distributed Triangle Detection via Expander Decomposition
- Distributed approximation algorithms for weighted shortest paths
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- MST in Log-Star Rounds of Congested Clique
- Distributed MIS via All-to-All Communication
- Better Approximation Algorithms for the Graph Diameter
- Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
- Fast routing table construction using small messages
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- STACS 2005
