ISSN:
1573-2886
Keywords:
k-edge-connectivity
;
spanning networks
;
Steiner networks
;
Steiner ratio
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Given a set of points P in a metric space, let l(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 r = inf l(P) ∣ P for k ≥ 1. In this paper, we show that in any metric space, r ≥ 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, $$r_k \geqslant \sqrt 3 /2,\;\;r_3 \leqslant (\sqrt 3 + 2)/4$$ and $$r_4 \leqslant (7 + 3\sqrt 3 )/(9 + 2\sqrt 3 )$$ .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1009889023408
Permalink