An NC approximation algorithm for optimal k-edge connectivity augmentation
Weifa Liang, B.D. MaKay · 1999
Given an undirected graph G=(V, E/sub 0/) with |V|=n, and a feasible weighted edge set E such that G(V, E/sub 0//spl cup/E/sub 0//spl cup/E) is k-edge connected, the optimal k-edge connectivity augmentation problem is to find a subset S/spl sube/E such that G(V, E/sub 0//spl cup/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/spl ges/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/spl les/t/spl les/[log/sub 3/4/n]. If G is /spl lambda/-edge connected and 1/spl les//spl lambda/