Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

DOI10.1007/978-3-540-77120-3_48MaRDI QIDQ5387786zbMATH OpenOpenAlexFDO

Authors Qin Xin

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5442

zbMATH Keywords

design and analysis of algorithmsdistributed computingnetworksrendezvousstrongly universal exploration sequences

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Analysis of algorithms (68W40)

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+frac1lambda)})$-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 $lambdagg1$ 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}.

Recommendations

• Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Treasure hunt with advice
• Treasure hunt with barely communicating agents
• Treasure hunt in graph using pebbles

Cites work

• Algorithms and Computation
• Asynchronous deterministic rendezvous in graphs
• Collisions Among Random Walks on a Graph
• Deterministic rendezvous in graphs
• Deterministic rendezvous in graphs
• Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
• How to Meet in Anonymous Network
• Undirected ST-connectivity in log-space

Cited in

(6)

• Advice complexity of treasure hunt in geometric terrains
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
• scientific article; zbMATH DE number 7561402 (Why is no real title available?)
• Deterministic treasure hunt and rendezvous in arbitrary connected graphs
• Self-stabilizing graph exploration by a single agent

This page was built for publication: Faster Treasure Hunt and Better Strongly Universal Exploration Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387786)