Evènement pour le 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.  
OrateurDominik Pajak 
UrlUniversity of Cambridge 

Aucun document lié à cet événement.

Retour à l'index