TY - JOUR
T1 - On Shortest k-Edge-Connected Steiner Networks in Metric Spaces
AU - Du, Xiufeng
AU - Hu, Xiaodong
AU - Jia, Xiaohua
PY - 2000
Y1 - 2000
N2 - 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).
AB - 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).
KW - K-edge-connectivity
KW - Spanning networks
KW - Steiner networks
KW - Steiner ratio
UR - http://www.scopus.com/inward/record.url?scp=0042640485&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0042640485&origin=recordpage
M3 - 21_Publication in refereed journal
VL - 4
SP - 99
EP - 107
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 1
ER -