Steiner tree heuristic in the Euclidean d-space using bottleneck distances
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Lorenzen_2016_Bottleneck_distances
Indsendt manuskript, 308 KB, PDF-dokument
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 | |
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 | Rusland |
By | St. Petersborg |
Periode | 05/06/2016 → 08/06/2016 |
Navn | Lecture notes in computer science |
---|---|
Vol/bind | 9685 |
ISSN | 0302-9743 |
- Det Natur- og Biovidenskabelige Fakultet
Forskningsområder
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 162414935