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

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