Distributed distance approximation
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 7650885 (Why is no real title available?)
- 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 faster distributed single-source shortest paths algorithm
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- Algebraic methods in the congested clique
- An information statistics approach to data stream and communication complexity
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Approximation of distances and shortest paths in the broadcast congest clique
- Communication Complexity
- Detecting cliques in CONGEST networks
- Distributed Spanner Approximation
- Distributed algorithms for network diameter and girth
- Distributed approximation algorithms for weighted shortest paths
- Distributed distance computation and routing with small messages
- Distributed exact shortest paths in sublinear time
- Distributed exact weighted all-pairs shortest paths in \(\widetilde{O}(n^{5/4})\) rounds
- Distributed exact weighted all-pairs shortest paths in near-linear time
- Distributed verification and hardness of distributed approximation
- Efficient distributed source detection with limited bandwidth
- Euclidean minimum spanning trees and bichromatic closest pairs
- Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
- Extreme Distances in Multicolored Point Sets
- FINDING k FARTHEST PAIRS AND k CLOSEST/FARTHEST BICHROMATIC PAIRS FOR POINTS IN THE PLANE
- Fast Approximate Shortest Paths in the Congested Clique
- 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
- Hopsets with constant hopbound, and applications to approximate shortest paths
- Improved distributed algorithms for exact shortest paths
- Near-linear lower bounds for distributed distance computations, even in sparse networks
- Near-optimal approximate shortest paths and transshipment in distributed and streaming models
- Networks cannot compute their diameter in sublinear time
- New bounds for approximating extremal distances in undirected graphs
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- On some fine-grained questions in algorithms and complexity
- On the complexity of k-SAT
- On the distributional complexity of disjointness
- On the power of the congested clique model
- Optimal distributed all pairs shortest paths and applications
- Planar diameter via metric compression
- Quadratic and near-quadratic lower bounds for the CONGEST model
- Reachability and shortest paths in the broadcast CONGEST model
- Single-Source Shortest Paths in the CONGEST Model with Improved Bound
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Towards tight approximation bounds for graph diameter and eccentricities
- Two applications of information complexity
This page was built for publication: Distributed distance approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6834015)
