Ansatte – Københavns Universitet

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

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

Dokumenter

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.
OriginalsprogEngelsk
TitelExperimental Algorithms : 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
RedaktørerAndrew V. Goldberg, Alexander S. Kulikov
Antal sider14
ForlagSpringer
Publikationsdato2016
Sider217-230
ISBN (Trykt)978-3-319-38850-2
ISBN (Elektronisk)978-3-319-38851-9
DOI
StatusUdgivet - 2016
Begivenhed 15th International Symposium on Experimental Algorithms - St. Petersborg, Rusland
Varighed: 5 jun. 20168 jun. 2016
Konferencens nummer: 15

Konference

Konference 15th International Symposium on Experimental Algorithms
Nummer15
LandRusland
BySt. Petersborg
Periode05/06/201608/06/2016
NavnLecture notes in computer science
Vol/bind9685
ISSN0302-9743

Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk


Ingen data tilgængelig

ID: 162414935