关键词: 分层法, 最大流, 流网络, 最小割, 网络分层

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