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

Статья опубликована в журнале из списка RSCI Web of Science

Работа с статьей


[1] Горбунов К. Ю., Любецкий В. А. Линейный алгоритм кратчайшей перестройки графов при разных ценах операций // Информационные процессы. — 2016. — Т. 16, № 2. — С. 223–236. Предлагается новый эффективный по времени и памяти алгоритм решения задачи о наиболее экономном (т.е. с наименьшей суммарной ценой) преобразовании любого ориентированного графа, являющегося дизъюнктным объединением цепей и циклов, в любой другой граф этого вида. Доказаны корректность алгоритма (т.е. он всегда выдаёт минимум функционала суммарной цены) и линейная оценка на время и память его работы.

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть