On strongly connected digraphs with bounded cycle length

DOI10.1016/0166-218X(95)00105-ZMaRDI QIDQ1923587zbMATH OpenOpenAlexFDO

Authors Samir Khuller, Balaji Raghavachari, Neal E. Young

Publication date 7 April 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

approximation algorithmcyclemaximum matchingminimum bipartite edge coverstrongly connected digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• On complete strongly connected digraphs with the least number of 3-cycles
• Approximating the minimum strongly connected subgraph via a matching lower bound
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• Some approaches to a conjecture on short cycles in digraphs

Cites work

• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• An Algorithm for a Minimum Cover of a Graph
• An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
• An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
• Approximating the Minimum Equivalent Digraph
• Easy problems for tree-decomposable graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• The Transitive Reduction of a Directed Graph

Cited in

(18)

• The minimum spanning strong subdigraph problem is fixed parameter tractable
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• On \(k\)-strong and \(k\)-cyclic digraphs
• Sparse certificates for 2-connectivity in directed graphs
• Dual power assignment via second Hamiltonian cycle
• On complete strongly connected digraphs with the least number of 3-cycles
• Structure of cycles in minimal strong digraphs
• DAG-width and circumference of digraphs
• Strongly connected spanning subgraph for almost symmetric networks
• Approximating Transitive Reductions for Directed Networks
• On longest cycles and strongly linking vertex sets
• On strong digraphs with a prescribed ultracenter
• Loop conditions for strongly connected digraphs
• Approximating minimum representations of key Horn functions
• 1.61-approximation for min-power strong connectivity with two power levels
• A characterization of positive spanning sets with ties to strongly edge-connected digraphs
• Dual-based approximation algorithms for cut-based network connectivity problems
• Inferring (biological) signal transduction networks via transitive reductions of directed graphs

This page was built for publication: On strongly connected digraphs with bounded cycle length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923587)