On strongly connected digraphs with bounded cycle length
From MaRDI portal
Publication:1923587
DOI10.1016/0166-218X(95)00105-ZzbMath0859.05057OpenAlexW3100826043MaRDI QIDQ1923587
Samir Khuller, Neal E. Young, Balaji Raghavachari
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
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)
Related Items (11)
Approximating Transitive Reductions for Directed Networks ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Dual power assignment via second Hamiltonian cycle ⋮ Inferring (biological) signal transduction networks via transitive reductions of directed graphs ⋮ Dual-based approximation algorithms for cut-based network connectivity problems ⋮ 1.61-approximation for min-power strong connectivity with two power levels ⋮ 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 ⋮ DAG-Width and Circumference of Digraphs ⋮ Strongly Connected Spanning Subgraph for Almost Symmetric Networks ⋮ Approximating Minimum Representations of Key Horn Functions
Cites Work
- Unnamed Item
- Unnamed Item
- An Algorithm for a Minimum Cover of a Graph
- Easy problems for tree-decomposable graphs
- An Algorithm for Finding a Minimal Equivalent Graph of a Digraph
- Approximating the Minimum Equivalent Digraph
- An Algorithm for Finding a Minimum Equivalent Graph of a Digraph
- The Transitive Reduction of a Directed Graph
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
This page was built for publication: On strongly connected digraphs with bounded cycle length
