๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Euclidean Steiner minimum trees: An improved exact algorithm

โœ Scribed by Winter, Pawel; Zachariasen, Martin

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
296 KB
Volume
30
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

Faster exact algorithms for steiner tree
Faster exact algorithms for steiner trees in planar networks
โœ Marshall Bern ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 739 KB

We improve the time and space complexities of dynamic programming algorithms that compute optimal Steiner trees spanning nodes in planar networks. Our algorithms have special application to the rectilinear Steiner problem.