Steiner tree heuristic in the Euclidean d-space using bottleneck distances
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Lorenzen_2016_Bottleneck_distances
Submitted manuscript, 308 KB, PDF document
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 | |
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 |
---|---|
Nummer | 15 |
Land | Russian Federation |
By | St. Petersborg |
Periode | 05/06/2016 → 08/06/2016 |
Series | Lecture notes in computer science |
---|---|
Volume | 9685 |
ISSN | 0302-9743 |
- Faculty of Science - Steiner minimal tree, d-dimensional Euclidean space, heuristic, bottleneck distances
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 162414935