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

Stephan Sloth Lorenzen; Pawel Winter

doi:10.1007/978-3-319-38851-9_15

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

Stephan Sloth Lorenzen, Pawel Winter

Department of Computer Science

92 Downloads (Pure)

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.

Original language	English
Title of host publication	Experimental Algorithms : 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
Editors	Andrew V. Goldberg, Alexander S. Kulikov
Number of pages	14
Publisher	Springer
Publication date	2016
Pages	217-230
ISBN (Print)	978-3-319-38850-2
ISBN (Electronic)	978-3-319-38851-9
DOIs	https://doi.org/10.1007/978-3-319-38851-9_15
Publication status	Published - 2016
Event	15th International Symposium on Experimental Algorithms - St. Petersborg, Russian Federation Duration: 5 Jun 2016 → 8 Jun 2016 Conference number: 15

Conference

Conference	15th International Symposium on Experimental Algorithms
Number	15
Country/Territory	Russian Federation
City	St. Petersborg
Period	05/06/2016 → 08/06/2016

Series	Lecture notes in computer science
Volume	9685
ISSN	0302-9743

Keywords

Faculty of Science
Steiner minimal tree
d-dimensional Euclidean space
heuristic
bottleneck distances

Access to Document

10.1007/978-3-319-38851-9_15

Lorenzen_2016_Bottleneck_distancesSubmitted manuscript, 308 KB

Cite this

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

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

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

@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",

note = " 15th International Symposium on Experimental Algorithms, SEA 2016 ; Conference date: 05-06-2016 Through 08-06-2016",

}

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 -

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

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this