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(n2m 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(n3 log m log U log(nC)) with the wave implementation of the cost scaling algorithm, and to O(nm log(n2/m) log m log U log(nC)) with the use of dynamic trees. These bounds are better than the current bound of O(mS(n, m, nC) log U), where 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.
