Fast approximate shortest paths in the congested clique
From MaRDI portal
Recommendations
- Approximation of distances and shortest paths in the broadcast congest clique
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Distributed approximation algorithms for weighted shortest paths
Cites work
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
- A hierarchy of lower bounds for sublinear additive spanners
- All-Pairs Almost Shortest Paths
- All-pairs small-stretch paths
- Approximation of distances and shortest paths in the broadcast congest clique
- Better approximation algorithms for the graph diameter
- Congested Clique Algorithms for the Minimum Cut Problem
- Congested clique algorithms for graph spanners
- Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
- Distributed MIS via all-to-all communication
- Distributed algorithms for network diameter and girth
- Distributed approximation algorithms for weighted shortest paths
- Distributed exact weighted all-pairs shortest paths in near-linear time
- Distributed triangle detection via expander decomposition
- Efficient distributed source detection with limited bandwidth
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fast partial distance estimation and applications
- Fast routing table construction using small messages (extended abstract)
- Faster Approximation of Distances in Graphs
- Faster algorithms for all-pairs approximate shortest paths in undirected graphs
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Improved distributed algorithms for exact shortest paths
- Improved massively parallel computation algorithms for MIS, matching, and vertex cover
- Lessons from the congested clique applied to MapReduce
- MST in \(O(1)\) rounds of congested clique
- MST in log-star rounds of congested clique
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- On a routing problem
- On the power of the congested clique model
- Optimal deterministic routing and sorting on the congested clique
- Optimal distributed all pairs shortest paths and applications
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Powers of tensors and fast matrix multiplication
- Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
- STACS 2005
- Spanners and emulators with sublinear distance errors
- Sparse matrix multiplication and triangle listing in the congested clique model
- Thorup-Zwick emulators are universally optimal hopsets
- Time–Work Tradeoffs of the Single-Source Shortest Paths Problem
- Towards tight approximation bounds for graph diameter and eccentricities
- \((\Delta+1)\) coloring in the congested clique model
- ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
Cited in
(8)- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- The shortest path with at most / nodes in each of the series/parallel clusters
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Fault-tolerant graph realizations in the congested clique
- Exponentially Faster Shortest Paths in the Congested Clique
- Fast partial distance estimation and applications
- Congested Clique Algorithms for the Minimum Cut Problem
- Approximation of distances and shortest paths in the broadcast congest clique
This page was built for publication: Fast approximate shortest paths in the congested clique
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064057)
