A MAXIMUM FLOW ALGORITHM IN SMALL CAPACITY NETWORKS

The maximum flow problem is a classical combinatorial optimization problem. In this paper, a kind of small capacity networks is described, which arises in many applications, and a special algorithm for the maximum flow problem on this kind of networks is proposed. The algorithm is faster than algorithms for general maximum flow problems and it has broken the O（mn） time barrier of the maximum flow problem, so it is of much importance in theory and constitutes a more efficient algorithm for solving many real application problems. It is a trivial work to test whether a network is a small capacity network, so the algorithm of this paper is also useful for general maximum flow problems.