Euclidean Steiner Minimum Trees: An Improved Exact Algorithm

The Euclidean Steiner tree problem asks for a shortest network interconnecting a set of terminals in the plane. Over the last decade, the maximum problem size solvable within 1 h (for randomly generated problem instances) has increased from 10 to approximately 50 terminals. We present a new exact algorithm, called geosteiner96. It has several algorithmic modifications which improve both the generation and the concatenation of full Steiner trees. On average, geosteiner96 solves randomly generated problem instances with 50 terminals in less than 2 min and problem instances with 100 terminals in less than 8 min. In addition to computational results for randomly generated problem instances, we present computational results for (perturbed) regular lattice instances and public library instances.