NC approximation algorithms for 2-connectivity augmentation in a graph

Given an undirected graph G = (V, E) with |V| = n, and a feasible set E of m weighted edges on V, the optimal 2-edge (2-vertex) connectivity augmentation problem is to find a subset S ⊆ E such that G(V, E ⊂ S*) is 2-edge (2-vertex) connected and the weighted sum of edges in S* is minimized. We devise NC approximation algorithms for the optimal 2-edge connectivity and the optimal 2-vertex connectivity augmentation problems by delivering solutions within (1 +ln n)(l + ε) times optimum and within (1 + In n)(1 + e) log n times optimum when G is connected, respectively, where n is the number of 2-edge connected components of G, n is the number of biconnected components of G, and ε is a constant with 0 < ε < 1. Consequently, we find an approximation solution for the problem of the minimum 2-edge (biconnected) spanning subgraph on a weighted 2-edge connected (biconnected) graph in the same time and processor bounds