Parallel algorithms for ranking of trees

Ranking a tree is defined as a mapping ρ of the nodes to the set {1, 2, . . .} such that if there is a path from u to v and ρ(u)=ρ(v) then there is a node w on the path from u to v such that ρ(w)>ρ(u). The highest number assigned to the node is called the rank number of the mapping. A mapping ρ with the smallest rank number is called optimal ranking. The best known serial algorithm takes O(n) time for the optimal node ranking. However, the problem of finding the optimal tree ranking appears to be highly sequential. It remains open whether it is in NC. The paper proposes a fast parallel algorithm for finding approximate optimal node ranking of trees using O(logn) steps with n² processors on a CRCW PRAM and an efficient parallel algorithm using O(log²n) steps with n processors on a EREW model