Minimisation of Networks Based on Computational Geometry Data Structures

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F18%3APU128913" target="_blank" >RIV/00216305:26210/18:PU128913 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1109/ICUMT.2018.8631247" target="_blank" >http://dx.doi.org/10.1109/ICUMT.2018.8631247</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/ICUMT.2018.8631247" target="_blank" >10.1109/ICUMT.2018.8631247</a>

Result language
angličtina
Original language name
Minimisation of Networks Based on Computational Geometry Data Structures
Original language description
In this paper, we deal with a problem of finding the shortest connection of points placed in the Euclidean plane. The traditional strategy starts from the complete graph and finds its minimum spanning tree. However, this approach is proportional to the second power of the number of vertices, and therefore not very efficient. Additionally, if instead of the minimum spanning trees, minimum Steiner trees are considered, then the total length of the final network is decreased. Since the Steiner tree problem is NP-hard, in the case of large instances, heuristics must be used. Here, we propose a Delaunay triangulation-based deterministic heuristic and show that it gives very good results in short times.
Czech name
—
Czech description
—

Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
2018 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)
ISBN
978-1-5386-9361-2
ISSN
—
e-ISSN
—
Number of pages
5
Pages from-to
143-147
Publisher name
Neuveden
Place of publication
Moskva
Event location
Moskva
Event date
Nov 5, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000459238500050

Similar results(10)