Low Degree Spanning Trees of Small Weight

dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorRaghavachari, Balajien_US
dc.contributor.authorYoung, Nealen_US
dc.date.accessioned2004-05-31T22:24:50Z
dc.date.available2004-05-31T22:24:50Z
dc.date.created1994-01en_US
dc.date.issued1998-10-15en_US
dc.description.abstractGiven 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 [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)en_US
dc.format.extent271500 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/611
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3203en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-94-1en_US
dc.titleLow Degree Spanning Trees of Small Weighten_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-3203.ps
Size:
265.14 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-3203.pdf
Size:
206.49 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-3203.ps