The GeoSteiner program is currently the fastest program to calculate Steiner trees. It has been used to solve
problems with 10000 terminals to optimal. It is the result of two groups work. Pawel Winter and Martin
Zachariasen, both working at the University of Copenhagen, Department of Computer Science, and David M. Warme.
Pawel Winters seminal program GEOSTEINER started it all back in 1985 and was improved by Pawel Winter and
Martin Zachariasen in 1996, and published as "GeoSteiner96".
In 1993 D. S. Salowe and D. M. Warme, inspired and influenced by Winter,
published the Salowe-Warme algorithm. It used backtrack search to concatenate rectilinear FSTs. In 1998, Warme's
PhD dissertation described a new branch-and-cut code for finding minimum spanning trees in arbitrary hyper graphs,
which was applied to the FST concatenation problem for both rectilinear and Euclidean FSTs.
The first distribution of the combined code therefore represented the "third version" of each group's code, and it
was thus named GeoSteiner version 3.0. This and subsequent versions continue that naming convention.
The current commercial version is the GeoSteiner 4. The previous version GeoSteiner 3.1 is available for non-commercial
and educational purpose from the GeoSteiner homepage .
The GeoSteiner package solves the following NP-hard problems: