Хижнякова Е.В. Решение задачи построения графа с минимальным коэффициентом растяжения методом локального поиска

Рейтинг:   / 0

Подробности

Просмотров: 23

DOI: https://doi.org/10.15688/mpcm.jvolsu.2026.1.7

Екатерина Владимировна Хижнякова
Старший преподаватель кафедры компьютерных наук и экспериментальной математики, Волгоградский государственный университет

Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.

https://orcid.org/0000-0002-7914-9988

просп. Университетский, 100, 400062 г. Волгоград, Российская Федерация

Аннотация. Данная статья посвящена задаче построения графа с минимальным коэффициентом растяжения — характеристикой, отражающей степень искажения расстояний между вершинами. Поскольку эта проблема относится к классу NP-полных, то предложен алгоритм построения на основе метода локального поиска. Данный подход обеспечивает построение триангуляции с усредненным коэффициентом растяжения порядка 1,04.

Ключевые слова: коэффициент растяжения, локальный поиск, NP-полные задачи, граф, триангуляция Делоне.

Произведение «Решение задачи построения графа с минимальным коэффициентом растяжения методом локального поиска», созданное авторами по имени Хижнякова Е.В. публикуется на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

Цитата: Математическая физика и компьютерное моделирование. Том 29 № 1 2026, с. 77-86

Вложения:

Khizhnyakova.pdf URL: https://mp.jvolsu.com/index.php/ru/component/attachments/download/1447

17 Скачивания