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

• Veröffentlicht in: Проблемы управления и информатики
• Datum: 2008
• Hauptverfasser: Погорелый, С.Д., Бойко, Ю.В., Лозицкий, С.И., Гусаров, А.Д.
• Format: Artikel
• Sprache: Russian
• Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2008
• Schlagworte: Методы обработки информации
• Online Zugang: https://nasplib.isofts.kiev.ua/handle/123456789/209321
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Zitieren: Формализованные методы распараллеливания алгоритма Голдберга–Тарьяна / С.Д. Погорелый, Ю.В. Бойко, С.И. Лозицкий, А.Д. Гусаров // Проблемы управления и информатики. — 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.