Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
Author:
Open Access
- 13 June 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 331-340
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Distributed MST for constant diameter graphs2001
- Clique Is Hard to Approximate within n 1-o(1)2000
- A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube1999
- Fast Distributed Construction of Smallk-Dominating Sets and ApplicationsJournal of Algorithms, 1998
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning TreesSIAM Journal on Computing, 1998
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding BoundsSIAM Journal on Computing, 1997
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- An Optimal Synchronizer for the HypercubeSIAM Journal on Computing, 1989
- Graph spannersJournal of Graph Theory, 1989
- Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems1987