@inproceedings{c3f41912d82e451581e0537296ee6610,

title = "Parallel algorithms for ranking of trees",

abstract = "Ranking a tree is defined as a mapping rho of the nodes to the set (1, 2,...) such that if there is a path from u to v and rho (u)= rho (v) then there is a node w on the path from u to v such that rho (w)> rho (u). The highest number assigned to the node is called the rank number of the mapping. A mapping rho 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 n2 processors on a CRCW PRAM and an efficient parallel algorithm using O(log2n) steps with n processors on a EREW model.",

author = "Y. Liang and Dhall, {S. K.} and S. Lakshmivarahan",

note = "Publisher Copyright: {\textcopyright} 1990 IEEE.; 2nd IEEE Symposium on Parallel and Distributed Processing, SPDP 1990 ; Conference date: 09-12-1990 Through 13-12-1990",

year = "1990",

doi = "10.1109/SPDP.1990.143502",

language = "English",

series = "Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "26--31",

booktitle = "Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing 1990, SPDP 1990",

address = "United States",

}