小容量网络上的最大流算法

A MAXIMUM FLOW ALGORITHM IN SMALL CAPACITY NETWORKS

最大流问题是一类经典的组合优化问题 .描述了一种小容量网络 ,这种网络有很强的实际应用背景 .同时给出了专门求解这种网络上最大流问题的算法 .该算法比通用的算法快 .它已经突破了最大流问题的 O(mn)时间障碍 ,具有较强的理论意义 ,也为解决许多实际应用问题提供了更有效的算法 .同时 ,由于判断一个网络是否为小容量网络非常简单 ,因此该算法也具有普遍意义 .

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.