A Distributed Algorithm for the Maximum Flow Problem

This paper presents an asynchronous distributed algorithm for solving the maximum flow problem which is based on the preflow-push approach of Golberg-Tarjan. Each node in graph initially knows the capacities of outgoing and incoming adjacent arcs, the source nodes knows additionally the number of nodes in graph. Nodes execute the same algorithm, and exchange messages with neighbors until the maximum flow is established. The algorithm is applicable in cases of multiple sources and/or targets. We give also here some ideas to adjust our algorithm to dynamic changes of arc capacities. For a graph of n nodes and m arcs, our algorithm takes O(n²m) message complexity and O(n² ) time complexity