## Abstract

Let τ_{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 | 11-19 |

Number of pages | 9 |

DOIs | |

State | Published - 2003 |

Externally published | Yes |

Event | Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003 |

### Other

Other | Nineteenth Annual Symposium on Computational Geometry |
---|---|

Country/Territory | United States |

City | san Diego, CA |

Period | 6/8/03 → 6/10/03 |

## Keywords

- Approximation
- Discrete geometry
- Minimum spanning trees

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics