IMPROVED ALGORITHMS FOR BIPARTITE NETWORK FLOW

In this paper, network flow algorithms for bipartite networks are stud ied. A network G = (V, E) is called bipartite if its vertex set V can be partitioned into two subsets V-1 and V-2 such that all edges have o ne endpoint in V-1 and the other in V-2. Let n = \V\, n(1) = \V-1\, n( 2) = \V-2\, m = \E\ and assume without loss of generality that n(1) le ss than or equal to I n(2). A bipartite network is called unbalanced i f n(1) << n(2) and balanced otherwise. (This notion is necessarily imp recise.) It is shown that several maximum Bow algorithms can be substa ntially sped up when applied to unbalanced networks. The basic idea in these improvements is a two-edge push rule that allows one to ''charg e'' most computation to vertices in V-1, and hence develop algorithms whose running times depend on n(1) rather than n. For example, it is s hown that the two-edge push version of Goldberg and Tarjan's FIFO pref low-push algorithm runs in O(n(1)m + n(1)(3)) time and that the analog ous version of Ahuja and Orlin's excess scaling algorithm runs in O(n( 1)m + n(1)(2) log U) time, where U is the largest edge capacity. These ideas are also extended to dynamic tree implementations, parametric m aximum flows, and minimum-cost flows.