A 1.8 Approximation Algorithm for Augmenting Edge-Connectivity of a Graph from 1 to 2
We present a 1.8-approximation algorithm for the following NP-hard problem: Given a connected graph G = (V, epsilon) and an edge set E on V disjoint to epsilon, find a minimum-size subset of edges F subset of E such that (V, epsilon boolean OR F) is 2-edge-connected. Our result improves and significantly simplifies the approximation algorithm with ratio 1.875 + epsilon of Nagamochi.
approximation algorithms connectivity graphs