Loading...
Please wait, while we are loading the content...
Similar Documents
Worst-case ratios for degree-constrained trees (1995).
| Content Provider | CiteSeerX |
|---|---|
| Author | Fekete, Sandor P. Klemmstein, Monika |
| Abstract | We discuss problems of minimum degree-constrained trees T k , 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 ae k;m = 1 + m m+k\Gamma2 and give an O(n log(k + m))) algorithm that converts a T k+m into a T k such that w(T k ) ! ae k;m T k+m . For the special case of a planar point set with L 1 distances, this implies that we can find a T 3 with w(T3 ) w(Tmin ) 3 2 . |
| File Format | |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Worst-case Ratio Degree-constrained Tree Planar Point Complete Graph Kn Special Case Minimum Degree-constrained Tree Metric Satifying Triangle Inequality |
| Content Type | Text |
