Том 11, серия 2, номер 1, 2004 г., Стр. 11-25

УДК 519.8
А. Е. Бабурин, Э. Х. Гимади, Н. М. Коркишко
Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых  циклов минимального веса

Аннотация:
Рассматривается задача нахождения двух реберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном взвешенном графе, в котором для весов выполняется неравенство треугольника. Показано, что задача NP-трудна в сильном смысле. Предложены два приближенных алгоритма с временной сложностью $O(n^3)$ в случае, когда на ребрах графа задана одна весовая функция и когда заданы две весовые функции. Показано, что соответствующие оценки точности асимптотически (с ростом $n$) равны 9/4 и 12/5.

Бабурин А. Е. ¹
Гимади Э. Х. ¹
Коркишко Н. М. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru

Статья поступила 10 ноября 2003 г.