Click here for full text:
Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing
Zhang, Bin; Ward, Julie; Feng, Qi
HPL-2005-121
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
| 
Printable version
