A random NC algorithm for depth first search (Q1104756)

We present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithms is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is \(O(T_{MM}(n)\log^ 3 n)\), and the number of processors used is \(P_{MM}(n)\) where \(T_{MM}n)\) and \(P_{MM}(n)\) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.