Back to Search
Start Over
A distributed approximation algorithm for the minimum degree minimum weight spanning trees
- Source :
-
Journal of Parallel & Distributed Computing . Feb2008, Vol. 68 Issue 2, p200-208. 9p. - Publication Year :
- 2008
-
Abstract
- Abstract: Fischer proposes in [T. Fischer, Optimizing the degree of minimum weight spanning trees, Technical Report 93–1338, Department of Computer Science, Cornell University, Ithaca, NY, USA, 1993] a sequential algorithm to compute a minimum weight spanning tree of maximum degree at most in time for any constant , where is the maximum degree value of an optimal solution and n is the number of nodes in the network. In the present paper, we propose a distributed version of Fischer''s sequential algorithm with time complexity , requiring messages and space per node, where is the maximum degree of an initial minimum weight spanning tree. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*COMPUTER networks
*COMPUTER training
*TECHNICAL reports
Subjects
Details
- Language :
- English
- ISSN :
- 07437315
- Volume :
- 68
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Journal of Parallel & Distributed Computing
- Publication Type :
- Academic Journal
- Accession number :
- 28136179
- Full Text :
- https://doi.org/10.1016/j.jpdc.2007.07.005