Networks cannot compute their diameter in sublinear time
From MaRDI portal
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- A new approach to all-pairs shortest paths on real-weighted graphs
- A New Combinatorial Approach for Sparse Graph Problems
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- A tight unconditional lower bound on distributed randomwalk computation
- Communication Complexity
- Distributed Computing: A Locality-Sensitive Approach
- Distributed MST for constant diameter graphs
- Distributed verification and hardness of distributed approximation
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- scientific article; zbMATH DE number 1670814 (Why is no real title available?)
- scientific article; zbMATH DE number 1256679 (Why is no real title available?)
- Hundreds of impossibility results for distributed computing
- Information Bounds Are Weak in the Shortest Distance Problem
- Locality in Distributed Graph Algorithms
- Matrix multiplication via arithmetic progressions
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On the exponent of all pairs shortest path problem
- On the locality of bounded growth
- The price of being near-sighted
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Undirected single-source shortest paths with positive integer weights in linear time
Cited in
(33)- Near-linear lower bounds for distributed distance computations, even in sparse networks
- A note on hardness of diameter approximation
- Redundancy in distributed proofs
- Fooling views: a new lower bound technique for distributed computations under congestion
- Message lower bounds via efficient network synchronization
- Distinguishing views in symmetric networks: a tight lower bound
- Distributed distance computation and routing with small messages
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- Low-congestion shortcuts without embedding
- A distributed algorithm for directed minimum-weight spanning tree
- The complexity of data aggregation in directed networks
- Distributed algorithms for network diameter and girth
- The cost of unknown diameter in dynamic networks
- Distributed spanner approximation
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- scientific article; zbMATH DE number 7559107 (Why is no real title available?)
- Quantum advantage for the LOCAL model in distributed computing
- Redundancy in distributed proofs
- Approximation algorithms for min-distance problems
- Distributed Testing of Distance-k Colorings
- Distributed graph algorithms and their complexity: an introduction
- Sublinear-time quantum computation of the diameter in CONGEST networks
- Separating Sublinear Time Computations by Approximate Diameter
- Improved hardness of approximation of diameter in the CONGEST model
- Fast distributed algorithms for girth, cycles and small subgraphs
- Distributed distance approximation
- Quantum distributed complexity of set disjointness on a line
- Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
- On the complexity of algorithms with predictions for dynamic graph problems
- Computing minimum weight cycle in the CONGEST model
- Distance computations in the hybrid network model via oracle simulations
- Approximation algorithms for min-distance problems in DAGs
- Separating sublinear time computations by approximate diameter
This page was built for publication: Networks cannot compute their diameter in sublinear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743466)
