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 in time for any constant b>1, 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 O(n) space per node, where Δ is the maximum degree of an initial minimum weight spanning tree.