On shortest two‐connected Steiner networks with Euclidean distance

Journal Article


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 l2(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 l2(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 l2(P) as follows: (√3/2) ≤ inf{l2(P) | P} ≤ [(√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. © 1998 John Wiley & Sons, Inc. Networks 32: 133–140, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.