|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Линейный алгоритм кратчайшей перестройки графов при разных ценах операцийстатья
Статья опубликована в журнале из списка RSCI Web of Science
- Авторы: Горбунов К.Ю., Любецкий В.А.
- Журнал: Информационные процессы
- Том: 16
- Номер: 2
- Год издания: 2016
- Первая страница: 223
- Последняя страница: 236
- Аннотация: Предлагается новый эффективный по времени и памяти алгоритм решения задачи о наиболее экономном (т.е. с наименьшей суммарной ценой) преобразовании любого ориентированного графа, являющегося дизъюнктным объединением цепей и циклов, в любой другой граф этого вида. Доказаны корректность алгоритма (т.е. он всегда выдаёт минимум функционала суммарной цены) и линейная оценка на время и память его работы.
- Добавил в систему: Любецкий Василий Александрович