Том 14, серия 2, номер 2, 2007 г., Стр. 41-61
УДК 519.8
Э. Х. Гимади, Ю. В. Глазков, А. Н. Глебов
Алгоритмы приближённого решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2
Аннотация:
Рассматривается задача отыскания двух рёберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном графе с произвольно приписанными весами рёбер 1 и 2. Основной результат работы – описание полиномиальных алгоритмов с гарантированными оценками точности 26/21 и 6/5, наилучшими в настоящее время. Эти алгоритмы основаны на нахождении частичных туров с большим числом рёбер в графах специального вида.
Библ. 13.
Гимади Э. Х. 1
Глазков Ю. В. 1
Глебов А. Н. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: gim@math.nsc.ru
Статья поступила 18 августа 2007 г.
Исправленный вариант — 9 ноября 2007 г.
