AuthorsQ. Xin
EditorsT. Takeshi
TitleFaster Treasure Hunt, and Better Strongly Universal Exploration Sequences
Publication TypeProceedings, refereed
Year of Publication2007
Conference NameThe 18th International Symposium on Algorithms and Computation (ISAAC'07)
ISBN Number978-3-540-77118-0

We study the explicit deterministic treasure hunt problem in an n-vertex network. This problem was firstly introduced by Ta-Shma, and Zwick in \cite{TZ07} [SODA'07]. It is the variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. We obtain an O(n^{c(1+\frac{1}łambda})})-time solution for this problem, which significantly improves the currently best known result of running time O(n^{2c}) in \cite{TZ07}, where c is a fixed constant from the construction of an universal exploration sequence in \cite{R05,TZ07}, łambda is a constant integer and łambda ġ 1. The treasure hunt problem motivates the study of strongly universal exploration sequences. We give a better explicit construction of strongly universal exploration sequences than the one in \cite{TZ07}.

Citation KeySimula.ND.75