Abstract
Let G be an undirected graph and T be a spanning tree of G. In this paper, an efficient parallel algorithm is proposed for determining whether T is an unordered depth-first search tree of G. The proposed algorithm runs in O(m/p + log m) time using p processors on the EREW PRAM, where m is the number of edges contained in G. It is cost-optimal and achieves linear speedup.