A delaunay triangulation‐based heuristic for the euclidean steiner problem
J. E. Beasley, Fabrice Goffinet · Networks · 1994
Abstract 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. © 1994 by John Wiley & Sons, Inc.