Том 13, серия 1, номер 2, 2006 г., Стр. 11-20

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

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

Агеев А. А. ¹
Бабурин А. Е. ¹
Гимади Э. Х. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 27 сентября 2005 г.
Исправленный вариант — 5 апреля 2006 г.