| |
Click here for full text:
A Simultaneous Parametric Maximum-Flow Algorithm for Finding the Complete Chain of Solutions
Zhang, Bin; Ward, Julie; Feng, Qi
HPL-2004-189
Keyword(s): maximum flow; networks; parametric flow networks; graphs; optimization; selection; sequencing
Abstract: A natural extension of the maximum flow problem is the parametric maximum flow problem, in which some of the arc capacities in the network are functions of a single parameter /1, .Previous approaches to the problem compute the maximum flow for a given sequence of parameter values sequentially taking advantage of the solution at the previous parameter value to speed up the computation at the next. In this paper, we present a new Simultaneous Parametric Maximum Flow (SPMF) algorithm that finds the maximum flow and a minimum cut of an important class of parametric networks for all values of parameter /1, simultaneously. Instead of working with the original parametric network, a new non-parametric network is derived from the original and the SPMF gives a particular state of the flows in the derived network, from which the nested minimum-cuts under all /1, - values are derived in a single scan of the vertices in a sorted order. SPMF simultaneously discovers all breakpoints of /1, where the maximum flow as a step- function of /1, jumps. The maximum flows at these /1, -values are calculated in O(m) time from the minimum- cuts; m is the number of arcs. Generalization beyond bipartite networks is also shown.
15 Pages
Back to Index
|
Printable version
