Approximating Biconnectivity in Parallel

Consider the following NP-hard problems: Given a graph G , find minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G . Over the past few years, exciting sequential algorithms for approximating such minimum subgraphs have been produced 6],10]. The approximation factors are improved from 2 to 3/2 for both of the problems. Yet the techniques involved are all based on augmenting depth-first-search trees and no similar progress has been carried to the parallel context. This paper presents NC algorithms to achieve approximation factors of 3/2 + ε for these two problems without computing depth-first-search trees. Received June 21, 1995; revised December 24, 1996, and June 2, 1997.