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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

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 languageEnglish
Title of host publicationExperimental Algorithms : 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings
EditorsAndrew V. Goldberg, Alexander S. Kulikov
Number of pages14
PublisherSpringer
Publication date2016
Pages217-230
ISBN (Print)978-3-319-38850-2
ISBN (Electronic)978-3-319-38851-9
DOIs
Publication statusPublished - 2016
Event 15th International Symposium on Experimental Algorithms - St. Petersborg, Russian Federation
Duration: 5 Jun 20168 Jun 2016
Conference number: 15

Conference

Conference 15th International Symposium on Experimental Algorithms
Nummer15
LandRussian Federation
BySt. Petersborg
Periode05/06/201608/06/2016
SeriesLecture notes in computer science
Volume9685
ISSN0302-9743

    Research areas

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

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 162414935