Low degree spanning trees of small weight

Samir Khuller, Balaji Raghavachari, Neal Young

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PublisherAssociation for Computing Machinery
Pages412-421
Number of pages10
ISBN (Electronic)0897916638
DOIs
StatePublished - May 23 1994
Event26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada
Duration: May 23 1994May 25 1994

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129502
ISSN (Print)0737-8017

Conference

Conference26th Annual ACM Symposium on Theory of Computing, STOC 1994
Country/TerritoryCanada
CityMontreal
Period5/23/945/25/94

ASJC Scopus subject areas

  • Software

Cite this