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
» People
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing

Zhang, Bin; Ward, Julie; Feng, Qi


Keyword(s): maximum flow; networks; parametric flow networks; graphs; optimization; selection; sequencing

Abstract: Two new algorithms, SPMFsimple and SPMFfast, for finding the complete chain of solutions of the selection model are presented in this paper. A special kind of residual path, called a λ-directed simple residual path, is identified to be the only kind of residual path necessary for SPMFsimple. By augmenting the right amount of flows along the λ-directed simple residual paths, the new algorithms are monotone convergent. SPMFfast replaces the path-wise flow augmentation by flow-redistribution at each node, which provides a factor of ten speed-up for all the large datasets tested.

7 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.