Low-degree spanning trees of small weight

Samir Khuller*, Balaji Raghavachari, Neal Young

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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

Original languageEnglish (US)
Pages (from-to)355-368
Number of pages14
JournalSIAM Journal on Computing
Volume25
Issue number2
DOIs
StatePublished - Apr 1996

Keywords

  • Algorithms
  • Approximation algorithms
  • Geometry
  • Graphs
  • Spanning trees

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Low-degree spanning trees of small weight'. Together they form a unique fingerprint.

Cite this