| Abstract | Given n points in the plane, the degree-K spanning tree problemasks for a spanning tree of minimum 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
degree 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 computed in O(n) time.
The results are generalized to points in higher dimensions. It is
shown that for any d [greater than or equal to] 3, an arbitrary
collection of points in DimD contains a spanning 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.
(Also cross-referenced as UMIACS-TR-94-1)
|
