TY - JOUR

T1 - On strongly connected digraphs with bounded cycle length

AU - Khuller, Samir

AU - Raghavachari, Balaji

AU - Young, Neal

N1 - Funding Information:
* Corresponding author. Department of Computer Science, Dartmouth College, 6211 Sudikoff Laboratories, Hanover, NH 03755-3510, USA. E-mail: ney@dartmouth.edu. Part of this research was done while at School of ORIE, Cornell University, Ithaca NY 14853 and supported by l&a Tardos’ NSF PYI grant DDM-9157199. ’ Research supported by NSF Research Initiation Award CCR-9307462. 2 Research supported by NSF grant CCR-9409625.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0012297449&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0012297449&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(95)00105-Z

DO - 10.1016/0166-218X(95)00105-Z

M3 - Article

AN - SCOPUS:0012297449

SN - 0166-218X

VL - 69

SP - 281

EP - 289

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -