On shortest three-edge-connected Steiner networks with Euclidean distance Original Research Article

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 l3(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{l3(P)|P} be the infimum of this value over all point sets P in the plane. We show that for any P, 3/2⩽inf{l3(P)|P}⩽(3+3)/5, and there is a polynomial-time (5/3)-approximation algorithm for the problem. Moreover for those P whose points lie on the sides of its convex hull, l3(P)>(2+3)/4, and there exists a fully polynomial-time approximation scheme for the problem in this special case.