Evènement pour le groupe GT Graphes et Applications


Date 2006-04-28  14:00-15:00
TitreMobile Agent Rendezvous in a Synchronous Torus - Euripides Markou. 
RésuméWe consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking computational difference between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have o(log n) memory, while they can perform rendezvous with detection as long as they have one unmovable token and O(log n) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary n x m (respectively, n x n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a n x m torus. 
LieuSalle 075 
OrateurEuripides Markou 



Aucun document lié à cet événement.

Retour
Retour à l'index