A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem

DOI10.1016/S0020-0190(02)00476-3zbMath1173.68874OpenAlexW2020856645MaRDI QIDQ1007574

Hiroshi Nagamochi, Toshihide Ibaraki, Liang Zhao

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

zbMATH Keywords

approximation algorithmscycle contractionstrongly connected subgraph

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

On computing the 2-vertex-connected components of directed graphs ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ Dual-based approximation algorithms for cut-based network connectivity problems ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Computing the 2-blocks of directed graphs ⋮ Strongly Connected Spanning Subgraph for Almost Symmetric Networks

Cites Work

• Unnamed Item
• A linear-time algorithm for a special case of disjoint set union
• On strongly connected digraphs with bounded cycle length
• Approximation Algorithms for Several Graph Augmentation Problems
• Approximating the Minimum Equivalent Digraph