Simultaneous Parametric Maximum Flow Algorithm with Vertex Balancing

Zhang, Bin ; Ward, Julie ; Feng, Qi

HP Development Company

关键词: maximum flow;    networks;    parametric flow networks;    graphs;    optimization;    selection;    sequencing;   

RP-ID  :  HPL-2005-121

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

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