Fast Algorithms for Bipartite Network Flow
Dan Gusfield, Charles U. Martel, David Fernández‐Baca · SIAM Journal on Computing · 1987
We discuss network flow in a bipartite graph G with node sets S and T. We show that Karzanov’s algorithm runs in time $O(|S|^2 |T|)$ on G, and that the MPM algorithm can be modified to run in the same bound. For the common case that the degree of each node in T is bounded by a constant, we show that a modified version of the MPM algorithm runs in time $O(|S|^3 + |S||T|)$ on G. The importance of these results comes from the common occurrence of problems that can be modeled and solved using network flow on bipartite graphs where $|S| \ll |T|$. In many applications involving bounded degree on the nodes in T, $|T| = \theta (|S|^2 )$, and our results reduce the best bounds on bipartite flow from $O(|S|^6 )$ to $O(|S|^3 )$. We use our results on bipartite flow to obtain the fastest known bounds on several combinatorial problems, and mention several additional problems involving bipartite flow where $|S|$ is much smaller than $|T|$.