Алгоритмы приближённого решения задачи о двух коммивояжёрах в полном графе с весами рёбер 1 и 2

Рассматривается задача отыскания двух рёберно непересекающихся гамильтоновых циклов минимального суммарного веса в полном неориентированном графе с произвольно приписанными весами рёбер 1 и 2. Основной результат работы – описание полиномиальных алгоритмов с гарантированными оценками точности 26/21 и 6/5, наилучшими в настоящее время. Эти алгоритмы основаны на нахождении частичных туров с большим числом рёбер в графах специального вида. Библ. 13.