Improved algorithms for bipartite network flow

Ravindra K. Ahuja, James B. Orlin, Clifford Stein, Robert E. Tarjan

Research output: Contribution to journalArticle

108 Scopus citations

Abstract

In this paper, network flow algorithms for bipartite networks are studied. A network G = (V,E) is called bipartite if its vertex set V can be partitioned into two subsets V1 and V2 such that all edges have one endpoint in V1 and the other in V2. Let n = |V|, n1 = |V1|, n2 = |V2|, m = |E| and assume without loss of generality that n1≤n2. A bipartite network is called unbalanced if n1≪n2 and balanced otherwise. (This notion is necessarily imprecise.) It is shown 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 one to `charge' most computation to vertices in V1, and hence develop algorithms whose running times depend on n1 rather than n. For example, it is shown that the two-edge push version of Goldberg and Tarjan's FIFO preflow-push algorithm runs in O(n1m+n1 3) time and that the analogous version of Ahuja and Orlin's excess scaling algorithm runs in O(n1m+n1 2log U) time, where U is the largest edge capacity. These ideas are also extended to dynamic tree implementations, parametric maximum flows, and minimum-cost flows.

Original languageEnglish (US)
Pages (from-to)906-933
Number of pages28
JournalSIAM Journal on Computing
Volume23
Issue number5
DOIs
StatePublished - Jan 1 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Improved algorithms for bipartite network flow'. Together they form a unique fingerprint.

  • Cite this