Steiner tree heuristic in the Euclidean d-space using bottleneck distances

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

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. red. / Andrew V. Goldberg; Alexander S. Kulikov. Springer, 2016. s. 217-230 (Lecture notes in computer science, Bind 9685).

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Harvard

Lorenzen, SS & Winter, P 2016, Steiner tree heuristic in the Euclidean d-space using bottleneck distances. i AV Goldberg & AS Kulikov (red), Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. Springer, Lecture notes in computer science, bind 9685, s. 217-230, 15th International Symposium on Experimental Algorithms, St. Petersborg, Rusland, 05/06/2016. https://doi.org/10.1007/978-3-319-38851-9_15

APA

Lorenzen, S. S., & Winter, P. (2016). Steiner tree heuristic in the Euclidean d-space using bottleneck distances. I A. V. Goldberg, & A. S. Kulikov (red.), Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings (s. 217-230). Springer. Lecture notes in computer science Bind 9685 https://doi.org/10.1007/978-3-319-38851-9_15

Vancouver

Lorenzen SS, Winter P. Steiner tree heuristic in the Euclidean d-space using bottleneck distances. I Goldberg AV, Kulikov AS, red., Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. Springer. 2016. s. 217-230. (Lecture notes in computer science, Bind 9685). https://doi.org/10.1007/978-3-319-38851-9_15

Author

Lorenzen, Stephan Sloth ; Winter, Pawel. / Steiner tree heuristic in the Euclidean d-space using bottleneck distances. Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. red. / Andrew V. Goldberg ; Alexander S. Kulikov. Springer, 2016. s. 217-230 (Lecture notes in computer science, Bind 9685).

Bibtex

@inproceedings{6c4dee4949aa45b6a728310aad8beb01,
title = "Steiner tree heuristic in the Euclidean d-space using bottleneck distances",
abstract = "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. ",
keywords = "Faculty of Science, Steiner minimal tree, d-dimensional Euclidean space, heuristic, bottleneck distances",
author = "Lorenzen, {Stephan Sloth} and Pawel Winter",
year = "2016",
doi = "10.1007/978-3-319-38851-9_15",
language = "English",
isbn = "978-3-319-38850-2",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "217--230",
editor = "Goldberg, {Andrew V.} and Kulikov, {Alexander S.}",
booktitle = "Experimental Algorithms",
address = "Switzerland",
note = " 15th International Symposium on Experimental Algorithms, SEA 2016 ; Conference date: 05-06-2016 Through 08-06-2016",

}

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