On the Structure and Complexity of the 2-Connected Steiner Network Problem
in the Plane
Emily L. Luebke and J. Scott Provan, Department of Operations Research,
University of North Carolina
Abstract
We consider the problem of finding a minimum Euclidean length graph 2-connecting
a set of points in the plane. We show that the solution to this problem
is an edge-disjoint union of full Steiner trees. This has three important
corollaries. The first is a proof that the problem is NP-hard ---
even in the sense of finding a fully polynomial approximation scheme.
The second is a complete description of the solutions for 2SNPP for rectangular
arrays of lattice points. The third is a linear-time algorithm for
constructing an optimal solution to 2SNPP given its topological description.