# Worst-case ratios for degree-constrained trees

Fekete, Sandor P. and Klemmstein, Monika
(1995)
*Worst-case ratios for degree-constrained trees.*
**Published In:**
Proceedings of the 4th Biannual Twente Workshop on Graph Theory and Discrete Optimization 1995, pp. 103-106.

## Abstract

We discuss problems of minimum degree-constrained trees Tk, where each vertex of a complete graph Kn with a metric satifying triangle inequality is restricted to at most k neighbors. We show that for any k and m, the ratio w(Tk)/w(Tk+m) can be arbitrarily close to rhok,m=1 + m/(m+k-2) and give an O(nlog (k+m)) algorithm that converts a Tk+m into a Tk such that w(Tk)< rhok,m Tk+m. For the special case of a planar point set with L1 distances, this implies that we can find a T3 with w(T3)/w(Tmin) <= 3/2.

Download: |
Postscript
- Preprinted Version
Download (176kB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

ZAIK Number: | zpr95-204 |
---|---|

Depositing User: | Archive Admin |

Date Deposited: | 02 Apr 2001 00:00 |

Last Modified: | 19 Dec 2011 09:46 |

URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/204 |