GeoSteiner

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: Euclidean Steiner Tree Problem in the Plane, Rectilinear Steiner Tree Problem in the Plane, Minimum Spanning Tree Problem in Hyper graphs The code is written in ANSI C and requires no supplementary software or libraries. The code makes heavy use of linear programming (LP)


References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Fafianie, Stefan; Bodlaender, Hans; Nederlof, Jesper: Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions (2015)
  2. Brazil, Marcus; Graham, Ronald L.; Thomas, Doreen A.; Zachariasen, Martin: On the history of the Euclidean Steiner tree problem (2014)
  3. Fafianie, Stefan; Bodlaender, Hans L.; Nederlof, Jesper: Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions (2013)
  4. Van Laarhoven, Jon W.; Ohlmann, Jeffrey W.: A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in $\Re ^d $ (2011)
  5. Ernst, Michael D.; Perkins, Jeff H.; Guo, Philip J.; McCamant, Stephen; Pacheco, Carlos; Tschantz, Matthew S.; Xiao, Chen: The Daikon system for dynamic detection of likely invariants (2007)
  6. Peyer, Sven: Shortest paths and Steiner trees in VLSI routing (2007)
  7. Brazil, Marcus; Nielsen, Benny K.; Winter, Pawel; Zachariasen, Martin: Rotationally optimal spanning and Steiner trees in uniform orientation metrics (2004)
  8. Peyer, Sven; Zachariasen, Martin; Grove Jørgensen, David: Delay-related secondary objectives for rectilinear Steiner minimum trees. (2004)
  9. Althaus, Ernst; Polzin, Tobias; Daneshmand, Siavash Vahdati: Improving linear programming approaches for the Steiner tree problem (2003)
  10. Polzin, Tobias; Daneshmand, Siavash Vahdati: On Steiner trees and minimum spanning trees in hypergraphs (2003)
  11. Nielsen, Benny K.; Winter, Pawel; Zachariasen, Martin: On the location of Steiner points in uniformly-oriented Steiner trees. (2002)
  12. Nielsen, Benny K.; Winter, Pawel; Zachariasen, Martin: An exact algorithm for the uniformly-oriented Steiner tree problem (2002)
  13. Winter, Pawel: Optimal Steiner hull algorithm (2002)