A parametric maximum flow algorithm for bipartite graphs with applications

A parametric maximum flow algorithm for bipartite graphs with applications

0.00 Avg rating0 Votes
Article ID: iaor19981317
Country: Netherlands
Volume: 80
Issue: 1
Start Page Number: 226
End Page Number: 235
Publication Date: Jan 1995
Journal: European Journal of Operational Research
Authors:
Abstract:

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 nm. Examples are then given to show how to use this parametric algorithm to solve practical problems.

Reviews

Required fields are marked *. Your email address will not be published.