Authors | Q. Xin |

Editors | T. Takeshi |

Title | Faster Treasure Hunt, and Better Strongly Universal Exploration Sequences |

Status | Published |

Publication Type | Proceedings, refereed |

Year of Publication | 2007 |

Conference Name | The 18th International Symposium on Algorithms and Computation (ISAAC'07) |

Publisher | Springer |

ISBN Number | 978-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 Key | Simula.ND.75 |