Khizhnyakova E.V. Solving the Problem of Constructing a Graph with a Minimum Stretch Factor Using the Local Search Method
- Details
- Hits: 24
https://doi.org/10.15688/mpcm.jvolsu.2026.1.7
Ekaterina V. Khizhnyakova
Senior Lecturer, Department of Computer Sciences 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. This research focuses on the problem of constructing a graph with a minimum stretch factor, a characteristic reflecting the degree of distortion of the distances between vertices. Since this problem belongs to the class of NP-complete, an algorithm based on the local search method is proposed. Like other heuristic algorithms, the developed approach does not guarantee the best result, but it allows to find triangulations with SF about 1.041 (or losses about 4.1%). It is reasonable to build triangulations, since it is shown that the desired graph belongs to this class. The local search method involves choosing the first acceptable solution. Different initial solutions can lead to different local minima, i.e. results. When choosing a random triangulation as the initial one, the losses of resulting graph are about 5.7%. Thus, the algorithm can be used as a means of improving the existing triangulation. However, it has been experimentally confirmed that using the algorithm with the Delaunay triangulation as the initial one is the optimal initialization strategy, which allows to achieve the losses about 4.1%. An additional advantage of the algorithm is the support of an adaptive stopping criterion, which allows to complete calculations as soon as a triangulation with a predefined allowable stretch factor is found, or after a limited number of local transitions.
Key words: stretch factor, local search, NP-complete problems, graph, Delaunay triangulation.
Khizhnyakova E.V. Solving the Problem of Constructing a Graph with a Minimum Stretch Factor Using the Local Search Method is licensed under a Creative Commons Attribution 4.0 International License.
Citation in English: Mathematical Physics and Computer Simulation. Vol. 29 No. 1 2026, pp. 77-86
 Khizhnyakova.pdfURL: https://mp.jvolsu.com/index.php/en/component/attachments/download/1455 | 46 Downloads |