Skip to main content
eScholarship
Open Access Publications from the University of California

Low-degree spanning trees of small weight

  • Author(s): Khuller, S
  • Raghavachari, B
  • Young, N
  • et al.

Published Web Location

https://arxiv.org/abs/cs/0205043
No data is associated with this publication.
Abstract

Given n points in the plane, the degree-K spanning-tree problem asks 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 3 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 4 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 ≥ 3, an arbitrary collection of points in ℛd contains a spanning tree of degree 3 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 2 for these problems.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item