收缩邻居节点集方法求解有向网络的最大流问题

Contracting Neighbor-Node-Set Approach for Solving Maximum Flow Problem in Directed Network

最大流问题在许多领域有广泛的应用,然而随着网络规模的增加,传统的算法无法快速高效地求解最大流问题.对一个给定的有向网络,文中提出一种收缩邻居节点集的方法(CNA)求解其最大流.该方法通过收缩邻居节点集有效降低网络规模,使经典算法及改进算法可直接使用.首先给出收缩邻居节点集的条件,接着给出依据收缩条件构建目标网络的算法,最后利用经典算法求解目标网络的最大流以实现初始网络最大流的最优近似.实验结果表明CNA不仅平均能将目标网络的规模降至初始网络的一半,且能以较小的误差求得初始网络的最大流.

Maximum flow problem is widely applied in many fields. However, with the significant increase of network size, classic algorithms cannot solve maximum flow quickly and efficiently. In this paper, a method named Contracting Neighbor-node-set Approach （CNA） is presented to get its maximum flow approximately in a given directed flow network. Aiming at reducing the size of network, the method contracts some nodes and edges so that the classic algorithms can be used directly to approximately solve maximum flow problem with less time complexity. Firstly, the condition of contracting neighbor-node-set is given. Then, the algorithm is presented to construct the target network. Finally, the classic algorithms are applied on the target network to approximately get maximum flow of original network. The experimental results show that CNA not only obtains the maximum flow of original network with few errors, but also reduces tl^e scale of the target flow network to half size of the original flow network averagely.