On strongly connected digraphs with bounded cycle length

Samir Khuller, Balaji Raghavachari, Neal Young*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)281-289
Number of pages9
JournalDiscrete Applied Mathematics
Volume69
Issue number3
DOIs
StatePublished - 1996

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On strongly connected digraphs with bounded cycle length'. Together they form a unique fingerprint.

Cite this