А. Н. Глебов, Д. Ж. Замбалаева, А. А. Скретнева, “$2/3$-приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум”, Дискретн. анализ и исслед. опер., 2014, том 21, выпуск 6,страницы 11

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

$2/3$-приближённый алгоритм для несимметричной задачи о двух коммивояжёрах на максимум

А. Н. Глебов, Д. Ж. Замбалаева, А. А. Скретнева

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

Аннотация: Получен приближённый алгоритм с оценкой точности $2/3$ и кубической оценкой временнóй сложности для несимметричной задачи о двух коммивояжёрах на максимум, состоящей в поиске двух рёберно непересекающихся гамильтоновых циклов с максимальным суммарным весом рёбер в полном ориентированном графе. Ил. 5, библиогр. 7.

Ключевые слова: задача коммивояжёра, задача о двух коммивояжёрах, полиномиальный алгоритм, гарантированная оценка точности, ориентированный граф.

УДК: 519.172.2

Статья поступила: 02.12.2013
Переработанный вариант: 11.07.2014