ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2014, Vol. 51 ›› Issue (8): 1845-1853.doi: 10.7544/issn1000-1239.2014.20130184

Previous Articles     Next Articles

To Solve Maximum Flow Problem of Network with a Layering Method

Zhao Shu, Su Jianzhong, Liu Qianqian, Zhang Yanping   

  1. (School of Computer Science and Technology, Anhui University, Hefei 230601) (Key Laboratory of Intelligent Computing and Signal Processing (Anhui University), Ministry of Education, Hefei 230601)
  • Online:2014-08-15

Abstract: Maximum flow problem is a classical combinational optimization problem. With the growing of the network scale, it is the key to improve the efficiency of the algorithm for the maximum flow problem. For a given single-source single-sink network, a novel layer method for getting its maximum flow is proposed in this paper. Firstly, we transform the original directed network into a layer network. Then we compute the maximum flow for each sub-network which contains two adjacent levels of nodes in the layer network. Finally, the minimum value of each sub-network's maximum flow is regarded as the estimated maximum flow of the original network. The experimental results on different networks show the efficiency of the proposed method. The maximum flow error is only about 1% averagely. Meanwhile, the running time of our method is only 11% of the classical algorithm (the Ford-Fulkerson algorithm) averagely. And in the best condition, the running time of our method is 2% of the classical algorithm and 25% of the improved two-phase capacity scaling algorithm.

Key words: layering method, maximum flow, flow network, min-cut, the layer network

CLC Number: