Международная конференция
"Современные проблемы математики, информатики и биоинформатики",
посвященная 100-летию со дня рождения члена-корреспондента АН СССР
Алексея Андреевича Ляпунова
№ гос. регистрации - 0321103262, ISBN 978-5-905569-03-6

11 - 14 октября 2011 г., Академгородок, Новосибирск, Россия

Гимади Э.Х.  

Алгоритмы с оценками для некоторых трудных задач маршрутизации

В статье приводятся результаты исследований по обоснованию гарантированных и асимптотически точных оценок решения ряда трудных задач маршрутизации, для которых в общем случае не удается построить точные алгоритмы полиномиальной сложности (в предположении, что классы P  и NP  не совпадают). Основное внимание уделено задачам отысканиея в полном неориентированном взвешенном графе нескольких реберно непересекающихся маршрутов коммивояжера экстремального суммарного веса.