SOLVING THE PROBLEM OF CONSTRUCTING A GRAPH WITH A MINIMUM STRETCH FACTOR USING THE LOCAL SEARCH METHOD

Full abstract

Read the full 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.