Abstract Spanning Trees of Small Weight

Given n points in the plane, the degree-K span-ning tree problem asks for a spanning tree of min-imum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low- weight degree-K spanning trees for K>2. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree three whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of de-gree four whose weight is at most 1.25 times the weight of a minimum spanning tree. These results solve open problems posed by Papadimitriou and Vazirani. Moreover, if a minimum spanning tree is given as part of the input, the trees can be com-puted in O(n) time. The results are generalized to points in higher dimensions. It is shown that for any d 23, an ar-bitrary collection of points in R ~ contains a span-ning tree of degree three, whose weight is at most 5/3 times the weight of a minimum spanning tree. This is the first paper that achieves factors better than two for these problems