An adaptive distributed algorithm for the maximum flow problem in the underlying asynchronous network
Thuy Lien Pham, Minh N. Bùi, Ivan Lavallée, Si Hoàng · 2006
This paper presents a new adaptive distributed algorithm which solves the problem of finding a maximum flow in the underlying asynchronous network. Sequential processes, executing the same code over local data, exchange messages with neighbors to establish the max flow, and adapt themselves to any change of arc capacity in the network. This algorithm is derived to the case of multiple sources and/or sinks without adding virtual source and/or virtual sink. For a graph of V nodes and E arcs, the algorithm achieves O(n 2 m) message complexity and O(n 2 ) time complexity.