Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна

• Опубліковано в: : Проблемы управления и информатики
• Дата: 2008
• Автори: Погорелый, С.Д., Бойко, Ю.В., Лозицкий, С.И., Гусаров, А.Д.
• Формат: Стаття
• Мова: Російська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2008
• Теми: Методы обработки информации
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/209321
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна / С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров // Проблемы управления и информатики. — 2008. — № 5. — С. 110-120. — Бібліогр.: 9 назв. — рос.

Запропоновано метод трансформації алгоритму Голдберга–Тар’яна, який розв’язує важливу мережну задачу пошуку максимального потоку в орієнтованому графі. Сформовано концепцію його паралельної реалізації, а також відповідної схеми алгоритму, з використанням математичного апарату модифікованих систем алгоритмічних алгебр Глушкова (САА-М). Отримано дві удосконалені схеми алгоритму для запропонованого підходу. This paper presents the method of the optimization of Goldberg–Tarjan’s algorithm that solves an important maximum flow problem in a directed graph. A theoretical synthesis of the corresponding parallel scheme of the algorithm is done with the means of systems of modified algorithmic algebras developed by V.M.Glushkov. Two optimized schemes are obtained for the offered approach.