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.

Actions:

Download:	Postscript - Preprinted Version Download (176kB) | Preview
Editorial actions:	View Item (Login required)