A double scaling algorithm for the constrained maximum flow problem
The constrained maximum flow problem is to send the maximum possible flow from a source node to a sink node in a directed capacitated network subject to a budget constraint that the total cost of the flow can be at most D . In this research, we present a double scaling algorithm whose generic version runs in O ( n 2 m log m log U log ( nC ) ) time, where n is the number of nodes in the network; m, the number of arcs; C, the largest arc cost; and U , the largest arc capacity. This running time can be further reduced to O ( n 3 log m log U log ( nC ) ) with the wave implementation  of the cost scaling algorithm, and to O(nmlog(n2/m)logmlogUlog(nC)) O ( nm log ( n 2 / m ) log m log U log ( nC ) ) with the use of dynamic tree s. These bounds are better than the current bound of O ( mS ( n , m , nC ) log U ) , where S(n,m,nC) S ( n , m , nC ) is the time to find a shortest path from a single source to all other nodes where nonnegative reduced costs are used as arc costs.
scaling maximum flow networks and graphs minimum cost network flow