A Delaunay triangulation-based heuristic for the Euclidean Steiner problem (with F. Goffinet), Networks, vol.24, 1994, pp215-224.
In this paper we present a heuristic for the Euclidean Steiner problem. The basis of this heuristic is to use the Delaunay triangulation to generate candidate Steiner vertices and then to remove redundant Steiner vertices via the minimal spanning tree. This basic algorithm is incorporated into a simulated annealing framework. Computational results are given for a number of test problems drawn from the literature.