Approximating Unweighted Connectivity Problems in Parallel

Given an integer k and a k-edge-connected graph G=(V, E), we wish to find an E′⊆E of minimum size such that the graph (V, E′) is k-edge-connected. This problem is NP-hard and the best performance ratio achieved by known NC approximation algorithms is 2. For the special case where the input integer k is fixed to be 2, it is known that a performance ratio of 1. 5+ϵ for any ϵ>0 can be achieved by an NC approximation algorithm. This paper considers the more general case where k is polylogarithmic in the size of the input graph, and presents the first NC approximation algorithm with a performance ratio of 1. 924 for this case. We also consider the vertex analogue of this problem in which we require k-vertex-connectivity instead of k-edge-connectivity. We present the first NC approximation algorithm with a performance ratio of 1. 931 for the special case where the input integer k is fixed to be 3.

Authors

• Zhi-Zhong Chen

Keywords

No keywords are indexed for this paper.