Title: Memory efficient anonymous network exploration
Speaker: Leszek A. Gasieniec, U of Liverpool

Abstract:
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. This paper considers 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 work the emphasis is on memory efficient exploration
of anonymous graphs. We discuss in more detail three approaches: random walk,
rotor-router and basic walk, reviewing major relevant results, presenting recent
developments, and commenting on directions for further research.