On Minimum-Weight k-Edge Connected Steiner Networks on Metric Spaces |
| |
Authors: | D Frank Hsu Xiao-Dong Hu Guo-Hui Lin |
| |
Institution: | (1) Department of Computer and Information Sciences, Fordham University, Bronx, NY 10458-5198, USA, US;(2) Institute of Applied Mathematics, Chinese Academy of Sciences, P.O. Box 2734, Beijing 100080, P.R. China. e-mail: xdhu@amath3.amt.ac.cn, CN |
| |
Abstract: | For a given set of points P in a metric space, let w
k(P) denote the weight of minimum-weight k-edge connected Steiner network on P divided by the weight of minimum-weight k-edge connected spanning network on P, and let r
k=inf{w
k(P) |P}. We show in this paper that for any P, , for even k≥2 and , for odd k≥3. In particular, we prove that for any P in the Euclidean plane, w
4(P) and w
5(P) are greater than or equal to , and ; For any P in the rectilinear plane , for odd k≥5. In addition, we prove that there exists an O(|P|3)-time approximation algorithm for constructing a minimum-weight k-edge connected Steiner network which has approximation ratio of for even k and for odd k.
Received: August 21, 1997 Revised: February 5, 1998 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|