Khizhnyakova E.V. NP-completeness of the problem of constructing a graph with a minimum stretch factor

Details
Hits: 178

https://doi.org/10.15688/mpcm.jvolsu.2023.2.4

Ekaterina V. Khizhnyakova
Senior Lecturer, Department of Computer Science and Experimental Mathematics,
Volgograd State University
This email address is being protected from spambots. You need JavaScript enabled to view it.
https://orcid.org/0000-0002-7914-9988 
Prosp. Universitetsky, 100, 400062 Volgograd, Russian Federation

Abstract. In this paper, we consider the problem of constructing a planar connected weighted graph on a given set of points in such a way that the sum of the shortest paths between all pairs of vertices is the minimum possible. In other words, the problem of constructing a graph with a minimum stretch factor. The euclidean distance between the ends is taken as the weight of the edge. It is proved that such a problem is NP-complete. This problem arises when planning transport networks, since it is the stretch factor of the graph of the transport network that directly indicates the level of overrun of transport, which should be as small as possible in order to minimize the resources spent. But since this problem is NP-complete, a heuristic algorithm for solving the problem under consideration is proposed, which is based on sorting some simple paths and has a recursive character. This algorithm always builds a triangulation, since only in this class of graphs is it possible to solve the problem. A number of experiments have been carried out on the statistical study of the stretch factor of the triangulation constructed as a result of the operation of the above algorithm on randomly generated points. Experiments show that the losses are about 1.5–7.8% , and for real cities this parameter is about 30%.

Key words: NP-completeness, stretch factor, graph, triangulation, heuristic algorithm. 

Creative Commons License
NP-completeness of the problem of constructing a graph with a minimum stretch factor by Khizhnyakova E.V. is licensed under a Creative Commons Attribution 4.0 International License.

Citation in English: Mathematical Physics and Computer Simulation. Vol. 26 No. 2 2023, pp. 43-51

Attachments:
Download this file (2_2023-44-52.pdf) 2_2023-44-52.pdf
URL: https://mp.jvolsu.com/index.php/en/component/attachments/download/1092		200 Downloads