A Fully Polynomial Approximation Scheme for the Euclidean Steiner Augmentation
Problem
J. Scott Provan, Department of Operations Research, University of
North Carolina
Abstract
Euclidean Steiner Augmentation Problem has as input a connected set of
straight line segments drawn in the Euclidean plane, and has as output
the smallest set straight line segments, in terms of total Euclidean length,
whose addition will make the resulting set 2-edge connected. A fully
polynomial approximation scheme is given for this problem. Several
extensions and variants are also discussed.