Abstract
Consider that T· is a given spanning tree of an undirected graph G which contains n vertices and m (≥ n - 1) edges. In this paper, we propose an O(m/p+log m)-time parallel algorithm using p processors on the EREW PRAM model to determine whether T is a depth-first-search tree of G. Our algorithm is optimal in time complexity and speed-up.