Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
DOI10.1145/1007352.1007407zbMATH Open1192.68319OpenAlexW2172178473MaRDI QIDQ3580979FDOQ3580979
Publication date: 15 August 2010
Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1007352.1007407
Recommendations
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
- A fast distributed approximation algorithm for minimum spanning trees
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A distributed approximation algorithm for the minimum degree minimum weight spanning trees
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
- A linear-time optimal-message distributed algorithm for minimum spanning trees
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)
Cited In (15)
- Title not available (Why is that?)
- Fast deterministic distributed algorithms for sparse spanners
- Local MST computation with short advice
- Low-congestion shortcut and graph parameters
- A fast distributed approximation algorithm for minimum spanning trees
- Distributed Graph Algorithms and their Complexity: An Introduction
- Redundancy in distributed proofs
- Distributed MST for constant diameter graphs
- Randomized Lower Bound for Distributed Spanning-Tree Verification
- Low-congestion shortcuts without embedding
- Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Title not available (Why is that?)
- Single-source shortest paths in the CONGEST model with improved bounds
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
This page was built for publication: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3580979)
