Improved Algorithms for Bipartite Network Flow
Report ID: TR-338-91Author: Ahuja, Ravindra K. / Orlin, James B. / Stein, Clifford / Tarjan, Robert E.
Date: 1991-05-00
Pages: 42
Download Formats: |PDF|
Abstract:
In this paper, we study network flow algorithms for bipartite networks. A network $G^=^(V,E)$ is called $bipartite$ if its vertex set $V$ can be partitioned into two subsets $V sub 1$ and $V sub 2$ such that all edges have one endpoint in $V sub 1$ and the other in $V sub 2$. Let $n^=^|V^|,^n sub 1^=^|{V sub 1}|,^n sub 2^=^|{V sub 2}|,^m^=^|E^|$ and assume without loss of generality that $n sub 1^ <= ^ n sub 2$. We call a bipartite network $unbalanced$ if $n sub 1$ $<<$ $n sub 2$ and $balanced$ otherwise. (This notion is necessarily imprecise.) We show that several maximum flow algorithms can be substantially sped up when applied to unbalanced networks. The basic idea in these improvements is a $two-edge^push^rule$ that allows us to "charge" most computation to vertices in $V sub 1$, and hence develop algorithms whose running times depend on $n sub 1$ rather than $n$. For example, we show that the two-edge push version of Goldberg and Tarjan's FIFO preflow push algorithm runs in $O(n sub 1^m + n size 6 {3 over 1})$ time and that the analogous version of Ahuja and Orlin's excess scaling algorithm runs in $O(n sub 1^m + n size 6 {2 over 1}$ log $U)$ time, where $U$ is the largest edge capacity. We also extend our ideas to dynamic tree implementations, parametric maximum flows, and minimum-cost flows.
- This technical report has been published as
- Improved Algorithms for Bipartite Network Flow. Ravindra K. Ahuja, James B. Orlin, Clifford Stein and Robert E. Tarjan, SIAM J. Comput. 23 (1994) 906-923.