Many parallel algorithms for graph problems start with finding a
spanning tree and rooting the tree to define some structural
relationship on the vertices which can be used by following problem
specific computations. The generic procedure is to find an unrooted
spanning tree and then root the spanning tree using the Euler tour
technique. With a randomized work-time optimal unrooted spanning
tree algorithm and work-time optimal list ranking, finding rooted
spanning trees can be done work-time optimally on EREW PRAM w.h.p.
Yet the Euler tour technique assumes as ``given'' a circular
adjacency list, it is not without implications though to construct
the circular adjacency list for the spanning tree found on the fly by
a spanning tree algorithm. In fact our experiments show that this
``hidden'' step of constructing a circular adjacency list could take
as much time as both spanning tree and list ranking combined. In
this paper we present new efficient algorithms that find rooted
spanning trees without using the Euler tour technique and incur
little or no overhead over the underlying spanning tree algorithms.
We also present two new approaches that construct Euler tours
efficiently when the circular adjacency list is not given. One is a
deterministic PRAM algorithm and the other is a randomized algorithm
in the SMP model.The randomized algorithm takes a novel approach to
the problems of constructing Euler tour and rooting a tree. It
computes a rooted spanning tree first, then constructs a Euler tour
directly for the tree using depth-first traversal. The tour
constructed is cache-friendly with adjacent edges in the tour stored
in consequtive locations of an array so that prefix-sum (scan) can be
used for tree computations instead of the more expensive list-ranking.
