Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

HP.com home

Technical Reports


HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

A Simultaneous Parametric Maximum-Flow Algorithm for Finding the Complete Chain of Solutions

Zhang, Bin; Ward, Julie; Feng, Qi


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

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.