Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
On the power of one bit: How to explore a graph when you cannot backtrack?
du groupe Algorithmique Distribuée

Date 2014-11-24  14:00-15:00
TitreOn the power of one bit: How to explore a graph when you cannot backtrack? 
RésuméWe study the problem of exploration of an anonymous undirected graph with n vertices, m edges and diameter D by a single mobile agent. The agent does not know the incoming port when entering to a vertex thus it cannot backtrack its moves. Each vertex of the graph is endowed with a whiteboard on which the agent can store information. In this talk we will study tradeoffs between the exploration time and the existence of the internal memory available to the agent. We will first show an algorithm for an agent with 1 bit of memory completing exploration of any graph with stop in time O(m) using whiteboards of size O(log Delta) on each vertex with degree Delta. An oblivious agent (with no internal memory) can explore any graph in time O(m D) using whiteboards of size O(log Delta) by applying the rotor-router mechanism. We will show that, even with unbounded whiteboards, there is no algorithm for oblivious agents that is better than the rotor-router in the worst case by showing a Omega(n3) lower bound for a specific class of graphs. We will also observe that any oblivious agent cannot stop after completing the task. This shows separation between oblivious and non-oblivious agents in terms of the exploration time and the stop property.  
Lieu178 
OrateurDominik Pajak 
Emaildsp39@cl.cam.ac.uk 
UrlUniversity of Cambridge 



Aucun document lié à cet événement.

Retour
Retour à l'index