Skip to main content
A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set
Abstract
We consider the following problem: given a connected graph G = (V, ε E) and an additional edge set E, find a minimum size subset of edges F ⊆ E such that (V, ε ∪ F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2 and a practical running time.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.