TY - GEN

T1 - Low degree spanning trees of small weight

AU - Khuller, Samir

AU - Raghavachari, Balaji

AU - Young, Neal

N1 - Funding Information:
*Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742. Research supported by NSF Research Initiation Award CCR-9307462. E-mail : samir@cs. wad .edu. t Department of Computer Science, The University of Texas at Dallas, Box 830688, Richardson, TX 75083-0688. Email : rbk@utdallas. edu. $School of Operations Research and Industrial Engineer-ing, Cornell University, Ithaca, NY 14853-3801. Paqt of this work was done while at U MIACS and was supported in part by NSF grants CCR-8906949 and CCR-9111348. Email : ney~orie. cornell. edu.
Publisher Copyright:
© 1994 ACM.

PY - 1994/5/23

Y1 - 1994/5/23

N2 - 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 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 23, an arbitrary collection of points in R 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.

AB - 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 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 23, an arbitrary collection of points in R 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.

UR - http://www.scopus.com/inward/record.url?scp=0028013945&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028013945&partnerID=8YFLogxK

U2 - 10.1145/195058.195212

DO - 10.1145/195058.195212

M3 - Conference contribution

AN - SCOPUS:0028013945

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 412

EP - 421

BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994

PB - Association for Computing Machinery

T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994

Y2 - 23 May 1994 through 25 May 1994

ER -