Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
From MaRDI portal
Recommendations
- Distributed exact weighted all-pairs shortest paths in near-linear time
- A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
- Distributed approximation algorithms for weighted shortest paths
- Optimal distributed all pairs shortest paths and applications
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Faster distributed shortest path approximations via shortcuts
- Distributed algorithms for computing shortest pairs of disjoint paths
Cites work
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- 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 fast distributed approximation algorithm for minimum spanning trees
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- Almost-Tight Distributed Minimum Cut Algorithms
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Approximate distance oracles
- Approximation of distances and shortest paths in the broadcast congest clique
- Can quantum communication speed up distributed computation?
- Dense subgraphs on dynamic networks
- Distributed Computing: A Locality-Sensitive Approach
- Distributed algorithms for network diameter and girth
- Distributed approximate matching
- Distributed approximate maximum matching in the CONGEST model
- Distributed approximation algorithms for weighted shortest paths
- Distributed minimum cut approximation
- Distributed verification and hardness of distributed approximation
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Efficient distributed source detection with limited bandwidth
- Fast Approximate Shortest Paths in the Congested Clique
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Fast partial distance estimation and applications
- Fast routing table construction using small messages (extended abstract)
- Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
- Hardness of Distributed Optimization
- High-Probability Parallel Transitive-Closure Algorithms
- Improved distributed algorithms for exact shortest paths
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- Near-optimal distributed maximum flow (extended abstract)
- Near-optimal scheduling of distributed algorithms
- Networks cannot compute their diameter in sublinear time
- On a routing problem
- Optimal distributed all pairs shortest paths and applications
- Quadratic and near-quadratic lower bounds for the CONGEST model
- Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
- Sparse matrix multiplication and triangle listing in the congested clique model
This page was built for publication: Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5020729)
