GeoSteiner swMATH ID: 4320 Software Authors: David Warme; Pawel Winter; Martin Zachariasen Description: 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) Homepage: http://steiner.usmart.dk/geosteiner.html Programming Languages: C Related Software: SteinLib; CPLEX; SCIP; TSPLIB; SCIP-Jack; DIMACS; OR-Library; Treewidthlib; JuMP; Mosek; LEDA; KNITRO; ComputeTW; FindSteinerTree; SeDuMi; ESC/Java; Eclat; SIMPLIFY; JML; Daikon Cited in: 25 Documents Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study. Zbl 1411.90225Juhl, Daniel; Warme, David M.; Winter, Pawel; Zachariasen, Martin 2018 all top 5 Cited by 44 Authors 7 Zachariasen, Martin 5 Winter, Pawel 3 Brazil, Marcus N. 3 Nielsen, Benny K. 3 Oudet, Edouard 3 Thomas, Doreen Anne 2 Althaus, Ernst 2 Bodlaender, Hans L. 2 Bonafini, Mauro 2 Fafianie, Stefan 2 Koch, Thorsten 2 Nederlof, Jesper 2 Peyer, Sven 2 Polzin, Tobias 2 Ras, Charl J. 2 Rehfeldt, Daniel 2 Vahdati-Daneshmand, Siavash 1 Ernst, Michael D. 1 Graham, Ronald Lewis 1 Grove Jørgensen, David 1 Guo, Philip J. 1 Juhl, Daniel Dahl 1 Lin, Bo 1 Massaccesi, Annalisa 1 McCamant, Stephen 1 Monod, Anthea 1 Ohlmann, Jeffrey W. 1 Orlandi, Giandomenico 1 Pacheco-González, Carlos Gabriel 1 Pajor, Thomas 1 Perkins, Jeff H. 1 Rauterberg, Felix 1 Swanepoel, Konrad J. 1 Tschantz, Matthew S. 1 Uchoa, Eduardo 1 Van Laarhoven, Jon W. 1 Velichkov, Bozhidar 1 Volz, Marcus 1 Warme, David M. 1 Werneck, Renato F. 1 Wulff-Nilsen, Christian 1 Xiao, Chen 1 Yoshida, Ruriko 1 Ziegler, Sarah all top 5 Cited in 17 Serials 3 Computational Geometry 2 Mathematical Programming Computation 1 Archive for History of Exact Sciences 1 Discrete Applied Mathematics 1 Information Processing Letters 1 Applied Mathematics and Optimization 1 Journal of Optimization Theory and Applications 1 Networks 1 Science of Computer Programming 1 Operations Research Letters 1 Algorithmica 1 Discrete & Computational Geometry 1 SIAM Journal on Mathematical Analysis 1 Mathematical Programming. Series A. Series B 1 Journal of Heuristics 1 Interfaces and Free Boundaries 1 EURO Journal on Computational Optimization all top 5 Cited in 11 Fields 14 Combinatorics (05-XX) 12 Computer science (68-XX) 11 Operations research, mathematical programming (90-XX) 3 Calculus of variations and optimal control; optimization (49-XX) 3 Geometry (51-XX) 1 Algebraic geometry (14-XX) 1 Partial differential equations (35-XX) 1 Convex and discrete geometry (52-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Biology and other natural sciences (92-XX) Citations by Year