Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

Abstract

In this paper, we investigate the explicit deterministic treasure hunt problem in a $n$-vertex network. This problem was firstly introduced by Ta-Shma and Zwick in \cite{TZ07} [SODA'07]. Note also it is a variant of the well known rendezvous problem in which one of the robot (the treasure) is always stationary. In this paper, we propose an $O(n^{c(1+\frac{1}{\lambda })})$-time algorithm for the treasure hunt problem, which significantly improves the currently best known result of running time $O(n^{2c})$ in \cite{TZ07}, where $c$ is a constant induced from the construction of an universal exploration sequence in \cite{R05,TZ07}, and $\lambda \gg 1$ is an arbitrary large, but fixed, integer constant. The treasure hunt problem also motivates the study of strongly universal exploration sequences. In this paper, we also propose a much better explicit construction for strongly universal exploration sequences compared to the one in \cite{TZ07}.