Seminar on "Memory Efficient Graph Exploration" by L. Gasieniec of Liverpool University within Theory Pearls
Date: October 13, 2008 (Monday) at 13:15 to 15:00
Memory Efficient Graph Exploration
Leszek A. Gasieniec
Efficient search in unknown or unmapped environments is one of the fundamental problems
in graph algorithmics. Its applications range from robot navigation in hazardous environments
to rigorous exploration, indexing and analysis of digital data available on the Internet.
A large volume of search algorithms has been proposed under various assumptions about
the capability of mobile entities as well as the characteristics of the explored environment.
The environment is very often pictured as the two or higher dimensional Euclidean space
("geometric model"), where a mobile agent can freely traverse subject to potential obstacles;
or as a directed or undirected graph ("graph model") where the environment is represented
by a graph of connections in which discrete moves are permitted only along its arcs or edges.
The design of efficient exploration algorithms in the graph 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,
memory consumption, and the use of other computational resources such as tokens, messages,
energy, etc. We provide a condense summary of core algorithmic solutions in the field.
The emphasis is on memory efficient graph exploration methods including a detail study
of the "random walk", the "Propp machine", and the "basic walk".
This is followed by presentation of recent developments in the field and application of
discussed graph traversal methods in search for efficient solutions to other related
combinatorial problems. We conclude with a list of open problems in the field.
Room: E:2405
Last modified Dec 9, 2011 12:59 pm by Andrzej.Lingas@cs.lth.se
0227