A parallel approach for obtaining maximum flow in a network

摘要

Computing flow in a directed graph is a fundamental problem to which other programs can be reduced. The objective associated with the flow networks problem is to maximize the flow through the network. So it is usually studied within the field of Optimization. A parallel approach for obtaining maximum flow in a network is presented here. The concept of layered network is used here. The algorithm proceeds in two passes, forward and backward passes. Each node in a layer are processed in parallel. The time complexity of the algorithm is analyzed to be O(n2logkn).