Optimal parallel construction of Hamiltonian cycles and spanning trees in random graphs

We give tight bounds on the parallel complexity of some problems involving random graphs. Speci cally, we show that a Hamiltonian cycle, a breadth rst spanning tree, and a maximal matching can all be constructed in (log n) expected time using n = log n processors on the CRCW PRAM. This is a substantial improvement over the best previous algorithms, which required ((log log n) 2) time and n log 2 n processors. We then introduce a technique which allows us to prove that constructing an edge cover of a random graph from its adjacency matrix requires (log n) expected time on a CRCW PRAM with O(n) processors. Constructing an edge cover is implicit in constructing a spanning tree, a Hamiltonian cycle, and a maximal matching, so this lower bound holds for all these problems, showing that our algorithms are optimal. This new lower bound technique is one of the very few lower bound techniques known which apply to randomized CRCW PRAM algorithms, and it provides the rst nontrivial parallel lower bounds for these problems.