A parametric maximum flow algorithm for bipartite graphs with applications

Suppose we are given a capacitated bipartite network G with node sets S and T. In network G, the arc capacities are not fixed values but are functions of a single parameter λ, where λ is a continuous real variable. Our problem is to determine the minimum value of λ such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity O(nm² log(m/n)) is presented, where n is the number of nodes in S, m is the number of nodes in T and n ≤ m. Examples are then given to show how to use this parametric algorithm to solve practical problems.