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

Abstract

Запропоновано метод трансформації алгоритму Голдберга–Тар’яна, який розв’язує важливу мережну задачу пошуку максимального потоку в орієнтованому графі. Сформовано концепцію його паралельної реалізації, а також відповідної схеми алгоритму, з використанням математичного апарату модифікованих систем алгоритмічних алгебр Глушкова (САА-М). Отримано дві удосконалені схеми алгоритму для запропонованого підходу.

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.