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(nm2 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.
|頁（從 - 到）||226-235|
|期刊||European Journal of Operational Research|
|出版狀態||已出版 - 5 1月 1995|