Skip to main content
On strongly connected digraphs with bounded cycle length
Abstract
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. © 1996 Elsevier Science B.V.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.