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 bΔ~* + [log_bn] in time O (n~(4+1/ln b)) 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 O (Δn~(2+1/ln b)), requiring O (n~(3+1/ln b)) messages and O(n) space per node, where Δ is the maximum degree of an initial minimum weight spanning tree.