Detail publikace
Minimalizace sítí založená na datových strukturách počítačové geometrie
ŠEDA, M. ŠEDA, P.
Český název
Minimalizace sítí založená na datových strukturách počítačové geometrie
Anglický název
Minimisation of Networks Based on Computational Geometry Data Structures
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
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.
Český abstrakt
V tomto příspěvku se zabýváme problémem hledání nejkratšího spojení bodů umístěných v euklidovské rovině. Tradiční strategie začíná z úplného grafu a hledá k němu nejkratší kostru. Avšak složitost tohoto přístupu je úměrná druhé mocnině počtu vrcholů a není tedy příliš efektivní. Navíc pokud místo minimální kostry grafu uvažujeme minimální Steinerův strom, pak celková délka sítě se zkrátí. Protože Steinerův problém je NP-těžký, v případě velkých instancí je nutné použít heuristiky. V článku navrhujeme deterministickou heuristiku založenou na Delaunayho triangulaci a ukazujeme, že dává velmi dobré výsledky v krátkém čase.
Anglický abstrakt
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.
Klíčová slova česky
kostra grafu, Steinerův strom, NP-těžký problém, Voroného diagram, Delaunayho triangulace
Klíčová slova anglicky
spanning tree, Steiner tree, NP-hard problem, heuristic, Voronoi diagram, Delaunay triangulation
Vydáno
11.11.2018
Místo
Moskva
ISBN
978-1-5386-9361-2
Kniha
2018 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)
Strany od–do
143–147
Počet stran
5
BIBTEX
@inproceedings{BUT149746,
author="Miloš {Šeda} and Pavel {Šeda},
title="Minimisation of Networks Based on Computational Geometry Data Structures",
booktitle="2018 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)",
year="2018",
month="November",
pages="143--147",
address="Moskva",
isbn="978-1-5386-9361-2"
}