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
(14)- On computing the 2-vertex-connected components of directed graphs
- Finding strong components using depth-first search
- Computing the 2-blocks of directed graphs
- Strongly connected spanning subgraph for almost symmetric networks
- Dual-based approximation algorithms for cut-based network connectivity problems
- Capacity-preserving subgraphs of directed flow networks
- An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph
- Sparse certificates for 2-connectivity in directed graphs
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Minmax strongly connected subgraphs with node penalties
- The minimum spanning strong subdigraph problem is fixed parameter tractable
- Approximating the Minimum Equivalent Digraph
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)
