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.


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: [img] Postscript - Preprinted Version
Download (176kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
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