Premium
Euclidean Steiner minimum trees: An improved exact algorithm
Author(s) -
Winter Pawel,
Zachariasen Martin
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199710)30:3<149::aid-net1>3.0.co;2-l
Subject(s) - steiner tree problem , combinatorics , euclidean geometry , concatenation (mathematics) , algorithm , mathematics , approximation algorithm , spanning tree , computer science , euclidean distance , discrete mathematics , artificial intelligence , geometry
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. © 1997 John Wiley & Sons, Inc. Networks 30:149–166, 1997