А. А. Агеев, А. Е. Бабурин, Э. Х. Гимади, “Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса”, Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, выпуск 2,страницы 11

Эта публикация цитируется в 23 статьях

Полиномиальный алгоритм с оценкой точности 3/4 для отыскания двух непересекающихся гамильтоновых циклов максимального веса

А. А. Агеев, А. Е. Бабурин, Э. Х. Гимади

Институт математики им. С. Л. Соболева СО РАН

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