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: |
Download (176kB) | Preview |
---|---|
Editorial actions: | ![]() |
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 |