Steiner tree heuristic in the Euclidean d-space using bottleneck distances
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Steiner tree heuristic in the Euclidean d-space using bottleneck distances. / Lorenzen, Stephan Sloth; Winter, Pawel.
Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. ed. / Andrew V. Goldberg; Alexander S. Kulikov. Springer, 2016. p. 217-230 (Lecture notes in computer science, Vol. 9685).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Steiner tree heuristic in the Euclidean d-space using bottleneck distances
AU - Lorenzen, Stephan Sloth
AU - Winter, Pawel
N1 - Conference code: 15
PY - 2016
Y1 - 2016
N2 - Some of the most efficient heuristics for the Euclidean Steiner minimal tree problem in the d-dimensional space, d ≥2, use Delaunay tessellations and minimum spanning trees to determine small subsets of geometrically close terminals. Their low-cost Steiner trees are determined and concatenated in a greedy fashion to obtain a low cost tree spanning all terminals. The weakness of this approach is that obtained solutions are topologically related to minimum spanning trees. To avoid this and to obtain even better solutions, bottleneck distances are utilized to determine good subsets of terminals without being constrained by the topologies of minimum spanning trees. Computational experiments show a significant solution quality improvement.
AB - Some of the most efficient heuristics for the Euclidean Steiner minimal tree problem in the d-dimensional space, d ≥2, use Delaunay tessellations and minimum spanning trees to determine small subsets of geometrically close terminals. Their low-cost Steiner trees are determined and concatenated in a greedy fashion to obtain a low cost tree spanning all terminals. The weakness of this approach is that obtained solutions are topologically related to minimum spanning trees. To avoid this and to obtain even better solutions, bottleneck distances are utilized to determine good subsets of terminals without being constrained by the topologies of minimum spanning trees. Computational experiments show a significant solution quality improvement.
KW - Faculty of Science
KW - Steiner minimal tree
KW - d-dimensional Euclidean space
KW - heuristic
KW - bottleneck distances
U2 - 10.1007/978-3-319-38851-9_15
DO - 10.1007/978-3-319-38851-9_15
M3 - Article in proceedings
SN - 978-3-319-38850-2
T3 - Lecture notes in computer science
SP - 217
EP - 230
BT - Experimental Algorithms
A2 - Goldberg, Andrew V.
A2 - Kulikov, Alexander S.
PB - Springer
T2 - 15th International Symposium on Experimental Algorithms
Y2 - 5 June 2016 through 8 June 2016
ER -
ID: 162414935