A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov · ACM Transactions on Algorithms · 2009
We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = ( V , E ) and an edge set E on V disjoint to E , find a minimum-size subset of edges F ⊆ E such that ( V , E ∪ F ) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + ε of Nagamochi.