Paper Info
Title
Low-Degree Spanning Trees of Small Weight
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 $K2$. 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 \ge 3$, an arbitrary collection of points in $\Re^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.
Year
DOI
Venue
1996
10.1137/S0097539794264585
SIAM J. Comput.
Keywords
Field
DocType
low-degree spanning trees,open problem,spanning-tree problem,minimum weight,low-weight degree,small weight,higher dimension,arbitrary collection,spanning tree,approximation algorithms,geometry,algorithms,spanning trees,minimum spanning tree,graphs
Discrete mathematics,Combinatorics,Distributed minimum spanning tree,Minimum degree spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Spanning tree,Shortest-path tree,Kruskal's algorithm,Mathematics,Minimum spanning tree
Journal
Volume
Issue
ISSN
25
2
SIAM J. Computing 25(2):355-368 (1996)
Citations 
PageRank 
References 
29
2.80
16
Authors
3
Name
Order
Citations
PageRank
Samir Khuller14053368.49
Balaji Raghavachari2100177.77
Neal Young3373.66