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 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 be the infimum of this value over all point sets P in the plane. We show that for any P , , and there is a polynomial-time -approximation algorithm for the problem. Moreover for those P whose points lie on the sides of its convex hull, , and there exists a fully polynomial-time approximation scheme for the problem in this special case.
steiner networks spanning networks edge-connectivity approximation algorithms