Detail publikačního výsledku

Minimisation of Networks Based on Computational Geometry Data Structures

ŠEDA, M.; ŠEDA, P.

Originální název

Minimisation of Networks Based on Computational Geometry Data Structures

Anglický název

Minimisation of Networks Based on Computational Geometry Data Structures

Druh

Stať ve sborníku v databázi WoS či Scopus

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.

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

spanning tree, Steiner tree, NP-hard problem, heuristic, Voronoi diagram, Delaunay triangulation

Klíčová slova v angličtině

spanning tree, Steiner tree, NP-hard problem, heuristic, Voronoi diagram, Delaunay triangulation

Autoři

ŠEDA, M.; ŠEDA, P.

Rok RIV

2019

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

143

Strany do

147

Strany počet

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",
  pages="143--147",
  address="Moskva",
  doi="10.1109/ICUMT.2018.8631247",
  isbn="978-1-5386-9361-2"
}