Optimal randomized EREW PRAM algorithms for finding spanning forests

We present the first randomized O(log n) time and O(m + n) work EREW PRAM a lgorithm for finding a spanning forest of an undirected graph G = (V, E) wi th n vertices and m edges. Our algorithm is optimal with respect to time, w ork, and space. As a consequence we get optimal randomized EREW PRAM algori thms for other basic connectivity problems such as finding a bipartite part ition, finding bridges and biconnected components, finding Euler tours in E ulerian graphs, finding an ear decomposition, finding an open ear decomposi tion, finding a strong orientation, and finding an st-numbering, (C) 2001 A cademic Press.