An Efficient Algorithm for Minimum-Weigh
โ
J. Keijsper; R. Pendavingh
๐
Article
๐
1998
๐
Elsevier Science
๐
English
โ 280 KB
Given a directed graph D=(V, A) and a set S V, a bibranching is a set of arcs B A that contains a v&(V "S) path for every v # S and an S&v path for every v # V "S. In this paper, we describe a primal dual algorithm that determines a minimum weight bibranching in a weighted digraph. It has running ti