Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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.