Minimisation of Networks Based on Computational Geometry Data Structures

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Minimisation of Networks Based on Computational Geometry Data Structures

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Minimisation of Networks Based on Computational Geometry Data Structures

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20202 - Communication engineering and systems

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2018

Kód důvěrnosti údajů

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

Název statě ve sborníku

2018 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)

ISBN

978-1-5386-9361-2

ISSN

—

e-ISSN

—

Počet stran výsledku

5

Strana od-do

143-147

Název nakladatele

Neuveden

Místo vydání

Moskva

Místo konání akce

Moskva

Datum konání akce

5. 11. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000459238500050