Abstract
Let tau;K be the worst-case (supremum) ratio of the weight of the minimum degree-K spanning tree to the weight of the minimum spanning tree, over all finite point sets in the Euclidean plane. It is known that τ 2 = 2 and τ5 = 1. In STOC '94, Khuller, Raghavachari, and Young established the following inequalities: 1.103 < τ3 ≤ 1.5 and 1.035 < τ4 ≤ 1.25. We present the first improved upper bounds: τ3 < 1.402 and τ4 < 1.143. As a result, we obtain better approximation algorithms for Euclidean minimum bounded-degree spanning trees. Let τK(d) be the analogous ratio in d-dimensional space. Khuller et al. showed that τ3(d) < 1.667 for any d. We observe that τ 3(d) < 1.633.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 177-194 |
| Number of pages | 18 |
| Journal | Discrete and Computational Geometry |
| Volume | 32 |
| Issue number | 2 |
| DOIs | |
| State | Published - Sep 2004 |
| Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics