Evènement pour le groupe Algorithmique Distribuée


Date 2009-04-06  14:00-15:00
TitreMemory efficient anonymous graph exploration 
RésuméEfficient exploration of unknown or unmapped environments has become one of the fundamental problem domains in algorithm design. Its applications range from robot navigation in hazardous environments to rigorous searching, indexing and analysing digital data available on the Internet. A large number of exploration algorithms has been proposed under various assumptions about the capability of mobile (exploring) entities and various characteristics of the environment which are to be explored. Here we consider the "graph model", where the environment is represented by a graph of connections in which discrete moves are permitted only along its edges. Designing efficient exploration algorithms in this model has been extensively studied under a diverse set of assumptions, e.g., directed vs undirected graphs, anonymous nodes vs nodes with distinct identities, deterministic vs probabilistic solutions, single vs multiple agent exploration, as well as in the context of different complexity measures including the time complexity, the memory consumption, and the use of other computational resources such as tokens and messages. In this talk the emphasis is on memory efficient exploration of anonymous graphs. We discuss in greater detail three approaches: "random walk", "Propp machine" and "basic walk", reviewing major relevant results, presenting recent developments, and commenting on directions for further research.  
LieuSalle 178 
OrateurLeszek Gąsieniec 
UrlUniversity of Liverpool 



Aucun document lié à cet événement.

Retour
Retour à l'index