Detail publikace

Minimisation of Networks Based on Computational Geometry Data Structures

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

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.

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.

BibTex


@inproceedings{BUT149746,
  author="Miloš {Šeda} and Pavel {Šeda}",
  title="Minimisation of Networks Based on Computational Geometry Data Structures",
  annote="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.",
  booktitle="2018 10th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)",
  chapter="149746",
  howpublished="online",
  year="2018",
  month="november",
  pages="143--147",
  type="conference paper"
}