Title :
Space-Optimal Deterministic Rendezvous
Author :
Carrier, Fabienne ; Devismes, Stéphane ; Petit, Franck ; Rivierre, Yvan
Author_Institution :
VERIMAG, Univ. Joseph Fourier, Grenoble, France
Abstract :
In this paper, we address the deterministic rendezvous of mobile agents into any unoriented connected graph. The agents are autonomous, oblivious, move asynchronously. For this problem, we exhibit some time and space lower bounds as well as some necessary conditions. We also propose an algorithm that is space-optimal and asymptotically optimal in rounds.
Keywords :
graph theory; mobile robots; asymptotically optimal algorithm; mobile agents; space optimal algorithm; space optimal deterministic rendezvous; unoriented connected graph; Context modeling; Distributed computing; Labeling; Mobile agents; Mobile robots; Nominations and elections; Orbital robotics; Read-write memory; Space technology; Topology; Autonomous Agents; Mobile Robot Networks; Optimality; Rendezvous;
Conference_Titel :
Parallel and Distributed Computing, Applications and Technologies, 2009 International Conference on
Conference_Location :
Higashi Hiroshima
Print_ISBN :
978-0-7695-3914-0
DOI :
10.1109/PDCAT.2009.13
