A parallel algorithm for the minimum flow problem in bipartite networks
Laura Ciupală, Eleonor Ciurea · Annual Conference on Computers · 2008
In this paper, we develop a parallel implementation of the deficit scaling algorithm for minimum flow in bipartite networks. This algorithm performs a pull from an active node with a large deficit and with the smallest distance label from N1 at a time followed by pulls from several nodes in N2 in parallel. It runs in O(n12 log C log p) time using p = ⌈m/n1⌉ processors.