Approximating the minimum strongly connected subgraph via a matching lower bound
Adrian R. Vetta · Symposium on Discrete Algorithms · 2001
We present a 3/2-approximation algorithm for the problem of finding a minimum strongly connected spanning subgraph in a given directed graph. As a corollary we obtain a 3/2-approximation algorithm for the more general minimum equivalent digraph problem. The performance of our algorithm is measured against a lower bound obtained from a simple matching problem. The performance guarantee is optimal with respect to the lower bound.