Networks

On shortest two‐connected Steiner networks with Euclidean distance

Journal Article

Abstract

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

Address:

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 StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com 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.