К.Ю. Горбунов, В.А. Любецкий

Линейный алгоритм кратчайшей перестройки графов при разных ценах операций

Предлагается новый эффективный по времени и памяти алгоритм решения задачи о наиболее экономном (т.е. с наименьшей суммарной ценой) преобразовании любого ориентированного графа, являющегося дизъюнктным объединением цепей и циклов, в любой другой граф этого вида. Доказаны корректность алгоритма (т.е. он всегда выдаёт минимум функционала суммарной цены) и линейная оценка на время и память его работы.

КЛЮЧЕВЫЕ СЛОВА: линейный алгоритм, ориентированный граф, цепь, цикл, преобразование графа, цена операции, комбинаторная оптимизация