Том 11, серия 2, номер 1, 2004 г., Стр. 11-25
УДК 519.8
А. Е. Бабурин, Э. Х. Гимади, Н. М. Коркишко
Приближенные алгоритмы для нахождения двух реберно непересекающихся гамильтоновых циклов минимального веса
Аннотация:
Рассматривается задача нахождения двух реберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном взвешенном графе, в котором для весов выполняется неравенство треугольника. Показано, что задача NP-трудна в сильном смысле. Предложены два приближенных алгоритма с временной сложностью $O(n^3)$ в случае, когда на ребрах графа задана одна весовая функция и когда заданы две весовые функции. Показано, что соответствующие оценки точности асимптотически (с ростом $n$) равны 9/4 и 12/5.
Бабурин А. Е. 1
Гимади Э. Х. 1
Коркишко Н. М. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru
Статья поступила 10 ноября 2003 г.
|