caa a22 4500 475778057 CHVBK 20180406123636.0 cr unu---uuuuu 170329e20000901xx s 000 0 eng 10.1007/s003730070012 doi (NATIONALLICENCE)springer-10.1007/s003730070012 On Minimum-Weight k-Edge Connected Steiner Networks on Metric Spaces [Elektronische Daten] [D. Frank Hsu, Xiao-Dong Hu, Guo-Hui Lin] 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. Springer-Verlag Tokyo, 2000 Hsu D. Frank Department of Computer and Information Sciences, Fordham University, Bronx, NY 10458-5198, USA, US aut Hu Xiao-Dong 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 aut Lin Guo-Hui 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 aut https://doi.org/10.1007/s003730070012 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s003730070012 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hsu D. Frank Department of Computer and Information Sciences, Fordham University, Bronx, NY 10458-5198, USA, US aut NATIONALLICENCE 700 1- Hu Xiao-Dong 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 aut NATIONALLICENCE 700 1- Lin Guo-Hui 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 aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer