On finding minimal 2-connected subgraphs
Pierre Kelsen, Vijaya Ramachandran · Symposium on Discrete Algorithms · 1991
We present efficient parallel algorithms for the problems of finding a minimal 2-edge-connected spanning subgraph of a 2-edge-connected graph and finding a minimal biconnected spanning subgraph of a biconnected graph. The parallel algorithms for both problems run in polylog time using a linear number of PRAM processors. We also give sequential algorithms for these problems that run in time O(m+n log n) where n and m denote the number of vertices and edges, respectively, in the input graph.