A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem
From MaRDI portal
Publication:1007574
Recommendations
Cites work
- A linear-time algorithm for a special case of disjoint set union
- Approximating the Minimum Equivalent Digraph
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Approximation Algorithms for Several Graph Augmentation Problems
- On strongly connected digraphs with bounded cycle length
Cited in
(17)- The minimum spanning strong subdigraph problem is fixed parameter tractable
- Sparse certificates for 2-connectivity in directed graphs
- On strongly connected digraphs with bounded cycle length
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
- On computing the 2-vertex-connected components of directed graphs
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Strongly connected spanning subgraph for almost symmetric networks
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- scientific article; zbMATH DE number 1003248 (Why is no real title available?)
- Approximating the Minimum Equivalent Digraph
- Computing the 2-blocks of directed graphs
- Capacity-preserving subgraphs of directed flow networks
- Finding strong components using depth-first search
- Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms
- Dual-based approximation algorithms for cut-based network connectivity problems
- Minmax strongly connected subgraphs with node penalties
This page was built for publication: A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1007574)
