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

• Published in: Проблемы управления и информатики
• Date: 2008
• Main Authors: Погорелый, С.Д., Бойко, Ю.В., Лозицкий, С.И., Гусаров, А.Д.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2008
• Subjects: Методы обработки информации
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/209321
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна / С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров // Проблемы управления и информатики. — 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.