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. © 1998 Springer-Verkg New York Inc.link_to_subscribed_fulltex