An efficient algorithm for minimum-weight bibranching

Given a directed graph D = (V, A) and a set S subset of or equal to V, a bibranching is a set of area B subset of or equal to A that contains a v-(V\S) path for every v is an element of S and an S-v path for every v is an element of V\S. In this paper, we describe a primal-dual algorithm that determines a minimum weight bibranching in a weighted digraph. It has running time O(n'(m + n log n)), where m = \A\, n = \V\ and n' = min{\S\, \V\S\}. Thus, our algorithm obtains the best known bounds for two important special cases of the problem: bipartite edge cover and r-branching. (C) 1998 Academic Press.