A parallel algorithm for finding a maximum flow in 0-1 networks
Liwu Li, T.A. Marsland · 1987
We present a parallel algorithm for finding the maximum flow in 0-1-networks. Our design is for a mesh-connected processor array and is based on the observation that an augmenting path in a 0-1-network can be found in time proportional to the number of vertices in the given network, rather than to the number of edges. Let integer n be the number of vertices in a 0-1-network. The time complexity of the parallel algorithm is Ο (n2+ε), where ε can be any small positive real number.