Euclidean Steiner Minimum Trees: An Improved Exact Algorithm

Pawel Winter, Martin Zachariasen

Research output: Contribution to journalArticlepeer-review

73 Citations (Scopus)

Abstract

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. 
Original languageEnglish
Pages (from-to)149-166
Number of pages18
JournalNetworks
Volume30
Issue number3
DOIs
Publication statusPublished - 1998

Cite this