Draining Algorithm for the Maximum Flow Problem

A new augmenting path based algorithm called draining algorithm is proposed for the maximum flow problem in this letter. Unlike other augmenting path based algorithms which augment gradually the flow from zero-flow to the maximum flow, the proposed algorithm drains the redundant capacities out of the network to achieve the maximum flow. Experimental results shown the high efficiency of the proposed algorithm in near saturated network, thought it has a same computational complex with the traditional augmenting path approach for regular flow networks.