Optimal Tree Ranking is in NC.
Pilar de la Torre, Raymond Greenlaw, Teresa M. Przytycka · 1992
This paper places the optimal tree ranking problem in NC. A ranking is a labeling of the nodes with natural numbers such that if nodes u and v have the same label then there exists another node with a greater label on the path between them. An optimal ranking is a ranking in which the largest label assigned to any node is as small as possible among all rankings. An O(n) sequential algorithm is known. Researchers have speculated that this problem is P -complete. We show that for an n-node tree, one can compute an optimal ranking in O(log n) time using n 2 = log n CREW PRAM processors. In fact, our ranking is super critical in that the label assigned to each node is absolutely as small as possible. We achieve these results by showing that a more general problem, which we call the super critical numbering problem, is in NC. No NC algorithm for the super critical tree ranking problem, approximate or otherwise, was previously known; the only known NC algorithm for optimal tree ranking ...