A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem
From MaRDI portal
Publication:1007574
DOI10.1016/S0020-0190(02)00476-3zbMATH Open1173.68874OpenAlexW2020856645MaRDI QIDQ1007574FDOQ1007574
Authors: Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki 
Publication date: 23 March 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00476-3
Recommendations
Cites Work
- Approximating the minimum strongly connected subgraph via a matching lower bound
- A linear-time algorithm for a special case of disjoint set union
- Approximating the Minimum Equivalent Digraph
- 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
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Sparse certificates for 2-connectivity in directed graphs
- Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
- Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
- 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)
