An NC approximation algorithm for optimal k-edge connectivity augmentation

Given an undirected graph G=(V, E₀) with |V|=n, and a feasible weighted edge set E such that G(V, E₀∪E₀ ∪E) is k-edge connected, the optimal k-edge connectivity augmentation problem is to find a subset S⊆E such that G(V, E₀ ∪S) is k-edge connected and the weighted sum of the edges in S is minimum, where k is a fixed integer. Since this problem is NP-complete for k⩾2, in this paper we will focus on its approximation solution in the parallel environment. If G is (k-1)-edge connected, the solution delivered by our NC approximation algorithm is within either twice the optimum if k is even, or 2t times the optimum otherwise, where 1⩽t⩽[log_3/4n]. If G is λ-edge connected and 1⩽λ<k-1, the solution delivered by our approximation algorithm is 2α times the optimum, where α is defined as follows: (i) if k and λ are both odd or both even, then α=(k-λ)/2(t+1); (ii) if k is even and λ is odd, then α=t[k-λ/2]+[k-λ/2]; (iii) otherwise, α=t[k-λ/2]+[k-λ/2]