A 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

We consider the following NP-hard problem: given a connected graph G=(V,E)G=(V,E) and a link set E on V   disjoint to EE, find a minimum size subset of edges F⊆EF⊆E such that (V,E∪F)(V,E∪F) is 2-edge-connected. In G. Even et al. (2005) [2] we presented a 1.8-approximation for the problem. In this paper we improve the ratio to 1.5.

Research highlights► We give a 1.5-approximation algorithm for the problem of augmenting a connected graph to be 2-connected, using a minimum number of edges from a specified set of edges.