An efficient parallel algorithm for shifting the root of a depth first spanning tree
Prasoon Tiwari · Journal of Algorithms · 1986
Given a simple, connected, undirected graph G on n vertices and a depth first spanning tree (dfst) T of G with root t, the root-shifting problem is to find a dfst R of G with a specified root r. We present an O(log n) step algorithm for solving this problem using n3 processors on a parallel computer which does not permit concurrent writes but allows concurrent reads. We also discuss a processor allocation strategy for this algorithm which can be implemented without increasing the overall running time of the algorithm.