On shortest three-edge-connected Steiner networks with Euclidean distance

摘要

Given a set of points P on the Euclidean plane, we consider the problem of constructing a shortest three-edge-connected Steiner network of P. Let l(3)(P) denote the length of the shortest three-edge-connected Steiner network of P divided by the length of the shortest three-edge-connected spanning network of P, and let inf{l(3)(P) P} be the infimum of this value over all point sets P in the plane. We show that for any P, root 3/2 less than or equal to inf{l(3)(P) P} less than or equal to (3 + root 3)/5, and there is a polynomial-time (5/root 3)-approximation algorithm for the problem. Moreover for those P whose points lie on the sides of its convex hull, l(3)(P) > (2 + root 3)/4, and there exists a fully polynomial-time approximation scheme for the problem in this special case. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 16]