On strongly connected digraphs with bounded cycle length
type: Item
instance of: scholarly article
title: On strongly connected digraphs with bounded cycle length
zbMATH Open document ID: 0859.05057
DOI: 10.1016/0166-218X(95)00105-Z
author: Samir Khuller
author: Balaji Raghavachari
author: Neal E. Young
published in: Discrete Applied Mathematics
publication date: 1997-04-07T00:00:00Z
full work available at URL: dam
review text: Let \(G\) be a strongly connected digraph with cycles of length 3 or less. We wish to find a strongly connected spanning subgraph of \(G\) with the least number of edges. The authors show that this problem is equivalent to the minimum bipartite edge cover problem. This equivalence allows the authors to improve the performance of the best approximation algorithm to the general problem with no cycle bounds.
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 933102
zbMATH Keywords: maximum matching
zbMATH Keywords: strongly connected digraph
zbMATH Keywords: minimum bipartite edge cover
zbMATH Keywords: approximation algorithm
zbMATH Keywords: cycle
MaRDI profile type: Publication
cites work: The Transitive Reduction of a Directed Graph
cites work: Easy problems for tree-decomposable graphs
cites work: Q4198056
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
cites work: Approximating the Minimum Equivalent Digraph
cites work: Q5585020
cites work: An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
cites work: An Algorithm for a Minimum Cover of a Graph
OpenAlex ID: W3100826043
description: scientific article; zbMATH DE number 933102