Minimum-weight two-connected spanning networks (Q582215): Difference between revisions

Consider the problem of constructing a minimum-weight, two-connected network spanning all the points in a set V with symmetric nonnegative distance function satisfying the triangle inequality. The authors prove that the weight of an optimal traveling salesman cycle is no greater than 4/3 times the weight of an optimal two-connected solution, with examples which approach this bound arbitrarily closely. The results are extended to the variation of the problem where only a prespecified subset of points must be spanned.