| |
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
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.
|
|
cs
brown
edu