Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

Details Faster Treasure Hunt and Better Strongly Universal Exploration Sequences Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

2012-04-24

arxiv.org/abs/1204.5442v1

Computer Science

Data Structures and Algorithms

Scientific paper

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}.

Affiliated with

Also associated with

No associations

Rating

Faster Treasure Hunt and Better Strongly Universal Exploration Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Treasure Hunt and Better Strongly Universal Exploration Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Treasure Hunt and Better Strongly Universal Exploration Sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-520616