A distributed approximation algorithm for the minimum degree minimum weight spanning trees

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 h Delta* + [log(h) n] in time O (n(4+1/In) (h)) for any constant h > 1, where Delta* 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 O (Delta(2+1)(n)/(In) (h)). requiring O (n(3+1/In h)) messages and O(n) space per node, where Delta is the maximum degree of an initial minimum weight spanning tree. (c) 2007 Elsevier Inc. All rights reserved.