The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
Research output: Contribution to conference › Paper › Research › peer-review
Standard
The GeoSteiner software package for computing Steiner trees in the plane : an updated computational study. / Juhl, Daniel; Warme, David M.; Winter, Pawel; Zachariasen, Martin.
2014. Paper presented at 11th DIMACS Implementation Challenge, Providence, United States.Research output: Contribution to conference › Paper › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - CONF
T1 - The GeoSteiner software package for computing Steiner trees in the plane
T2 - 11th DIMACS Implementation Challenge
AU - Juhl, Daniel
AU - Warme, David M.
AU - Winter, Pawel
AU - Zachariasen, Martin
N1 - Conference code: 11
PY - 2014
Y1 - 2014
N2 - The GeoSteiner software package has for more than 10 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach --- allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. In this computational study we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using both the publicly available GeoSteiner 3.1 code base, and the commercial GeoSteiner 4.0 code base.
AB - The GeoSteiner software package has for more than 10 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach --- allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. In this computational study we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using both the publicly available GeoSteiner 3.1 code base, and the commercial GeoSteiner 4.0 code base.
KW - Faculty of Science
KW - Euclidean Steiner tree problem
KW - rectilinear Steiner tree problem
KW - fixed orientation Steiner tree problem
KW - exact algorithm
KW - computational study
M3 - Paper
Y2 - 4 December 2014 through 5 December 2014
ER -
ID: 137039853