Contracting Neighbor-Node-Set Approach for Solving Maximum Flow Problem in Directed Network
ZHAO Shu,XU Xian-Sheng,HUA Bo,ZHANG Yan-Ping
School of Computer Science and Technology,Anhui University,Hefei 230601 Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education,Anhui University,Hefei 230039
Abstract 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 the scale of the target flow network to half size of the original flow network averagely.
2013, Vol. 26 
