Improved Algorithms for Bipartite Network Flow

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.