Loading...
Please wait, while we are loading the content...
Similar Documents
Angewandte Mathematik Und Informatik Universit at Zu K Oln Worst-case Ratios for Degree-constrained Trees
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fekete, P. O. Klemmstein, Monika |
| Copyright Year | 1995 |
| Abstract | We discuss problems of minimum degree-constrained trees T k , where each vertex of a complete graph K n 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 k;m = 1 + m m+k?2 and give an O(n log(k + m))) algorithm that converts a T k+m into a T k such that w(T k) < k;m T k+m. For the special case of a planar point set with L 1 distances, this implies that we can nd a T 3 with w(T3) w(Tmin) 3 2 . |
| File Format | PDF HTM / HTML |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
