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.
No takes yet. Share an insight, caveat, or question.
Even et al. (2009) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: