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

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]