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

Datalogisk Institut

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.

Originalsprog	Engelsk
Titel	Experimental Algorithms : 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
Redaktører	Andrew V. Goldberg, Alexander S. Kulikov
Antal sider	14
Forlag	Springer
Publikationsdato	2016
Sider	217-230
ISBN (Trykt)	978-3-319-38850-2
ISBN (Elektronisk)	978-3-319-38851-9
DOI	https://doi.org/10.1007/978-3-319-38851-9_15
Status	Udgivet - 2016
Begivenhed	15th International Symposium on Experimental Algorithms - St. Petersborg, Rusland Varighed: 5 jun. 2016 → 8 jun. 2016 Konferencens nummer: 15

Konference

Konference	15th International Symposium on Experimental Algorithms
Nummer	15
Land/Område	Rusland
By	St. Petersborg
Periode	05/06/2016 → 08/06/2016

Navn	Lecture notes in computer science
Vol/bind	9685
ISSN	0302-9743

Emneord

Det Natur- og Biovidenskabelige Fakultet

Adgang til dokumentet

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

Lorenzen_2016_Bottleneck_distancesIndsendt manuskript, 308 KB

Citationsformater

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/rapport › Konferencebidrag i proceedings › Forskning › peer review

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

@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

Konference

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater