On shortest two-connected Steiner networks with Euclidean distance

✍ Scribed by Hsu, D. Frank; Hu, Xiao-Dong

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 137 KB
• Volume: 32
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/(sici)1097-0037(199809)32:2<133::aid-net6>3.0.co;2-c

✦ Synopsis

In this paper, we consider the problem of constructing the shortest two-connected Steiner network on the Euclidean plane. For a given set P of points on the Euclidean plane, let l 2 (P) denote the length of the shortest two-connected Steiner network on P divided by the length of the shortest two-connected spanning network on P. We prove that l 2 (P) Å 1, if any one of the following conditions is satisfied: (1) All points in P are on the sides of the convex hull of P;

(2) all points except one in P are on the sides of the convex hull of P; or (3) the cardinality of P is no greater than 5. Moreover, we obtain general lower and upper bounds for l 2 (P) as follows: ( 3/2) °inf{l 2 (P)ÉP} °2[( 3 / 2)/( 3 / 6)]. We also show that Christofides' heuristic for the traveling salesman problem can be used to design a polynomial-time algorithm for finding the shortest two-connected Steiner and spanning network with guaranteed worst-case performance ratio of 3 and 3 2 , respectively.