Simultaneous parametric maximum flow algorithm with vertex balancing

Two new algorithms, SPMF simple and SPMF fast, 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 SPMF simple. By augmenting the right amount of flows along the λ-directed simple residual paths, the new algorithms are monotone convergent. SPMF fast 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