A comment on Finding an Optimal Tree Searching Strategy in Linear Time. Shay Mozes, Krzysztof Onak and Oren Weimann. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 1096-1105   pdf version ppt presentation  

After this paper was published in the proceedings of SODA, we found a relevant sequence of papers on the tree ranking problem. The term tree ranking is essentially identical to the term strategy function used in our paper. The most relevant paper is "Optimal Edge Ranking of Trees in Linear Time" by T.W. Lam and F.L. Yue. This paper solves the edge ranking problem in linear time. While the high level descriptions of the algorithms in both papers are similar, the two solutions differ in the representation of visibility lists and choice of data structures. Unlike Lam and Yue's algorithm, our solution achieves linear running time without using "bit-tricks". Furthermore, we also show how to transform in linear time a ranking/strategy into the corresponding hierarchical decomposition of the tree.