%0 Journal Article
%J Discrete Applied Mathematics
%D 1996
%T On strongly connected digraphs with bounded cycle length
%A Khuller, Samir
%A Raghavachari,Balaji
%A Young,Neal
%X Given a directed graph G = (V, E), a natural problem is to choose a minimum number of the edges in E such that, for any two vertices u and v, if there is a path from u to v in E, then there is a path from u to v among the chosen edges. We show that in graphs having no directed cycle with more than three edges, this problem is equivalent to Maximum Bipartite Matching. This leads to a small improvement in the performance guarantee of the previous best approximation algorithm for the general problem.
%B Discrete Applied Mathematics
%V 69
%P 281 - 289
%8 1996/08/27/
%@ 0166-218X
%G eng
%U http://www.sciencedirect.com/science/article/pii/0166218X9500105Z
%N 3
%R 10.1016/0166-218X(95)00105-Z