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 931338, 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 b n ? in time O n 4 + 1 / ln b for any constant b>1 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) O ( n ) space per node, where ? ? is the maximum degree of an initial minimum weight spanning tree.
approximation algorithms minimum degree minimum weight spanning trees distributed algorithms