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 lambda, where lambda is a continuous real variable. Our problem is to determine the minimum value of lambda such that the maximum flow value in the corresponding network equals a given threshold. For this problem, an algorithm of time complexity O(nm(2) log(m/n)) is presented, where n is the number of nodes in S, m is the number of nodes in T and n less than or equal to m. Examples are then given to show how to use this parametric algorithm to solve practical problems.
