Given a directed bipartite graph G=(V,E) with a node set V={s}∪V1∪V2∪{t}, and an arc set E=E1∪E2∪E3, where E1={s}×V1, E2=V1×V2, and E3=V2×{t}. Chen (1995) presented an O(|V||E|log(|V|2|E|)) time algorithm to solve the parametric bipartite maximum flow problem. In this paper, we assume all arcs in E2 have infinite capacity [such a graph is called closure graph Hochbaum (1998)], and present a new approach to solve the problem, which runs in O(|V1||E|log(|V1|2|E|+2)) time using Gallo et al’s parametric maximum flow algorithm, see Gallo et al. (1989). In unbalanced bipartite graphs, we have |V1|<<|V2|, so, our algorithm improves Chens’s algorithm in unbalanced and closure bipartite graphs.
