@article{37c7290026244c75b0f446c750c698ee, title = "On Shortest k-Edge-Connected Steiner Networks in Metric Spaces", abstract = "Given a set of points P in a metric space, let lk (P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the shortest k-edge-connected spanning network on P, and let rk = inf{lk(P)|P} for k ≥ 1. In this paper, we show that in any metric space, rk ≥ 3/4 for k ≥ 2, and there exists a polynomial-time α-approximation for the shortest k-edge-connected Steiner network, where α = 2 for even k and α = 2 + 4/(3k) for odd k. In the Euclidean plane, rk ≥ √3/2, r3 ≤ (√3+2)/4 and r4 ≤ (7+3√3)/(9+2√3).", keywords = "K-edge-connectivity, Spanning networks, Steiner networks, Steiner ratio", author = "Xiufeng Du and Xiaodong Hu and Xiaohua Jia", year = "2000", language = "English", volume = "4", pages = "99--107", journal = "Journal of Combinatorial Optimization", issn = "1382-6905", publisher = "Springer New York LLC", number = "1", }