Towards a Poly($d$)-competitive Online Exploration Algorithm for (Planar) Strongly Connected Directed Graphs 
Gerhard Trippen
HKUST

Date: Friday October 29, 2004
Time 11-12
Venue: Room 3464, HKUST


Abstract
In this talk we will discuss the exploration problem
where a robot has to build a complete map of an unknown 
environment.We will briefly mention several models but 
consider the model of a strongly connected directed graph 
in more detail.Here the robot has to visit every edge and 
every node at least once but the number of edge traversals 
should be minimized.

Deng and Papadimitriou pointed out that $d$, the number of 
edges which must be added to make the graph Eulerian,
is a crucial parameter in this setting.
They showed polynomial lower bounds and an exponential algorithm.
Albers and Henzinger showed that most natural exploration algorithms
are also exponential, and were able to give a sub-exponential algorithm.
However, improving the lower or upper bounds seems very hard.

We are attempting to find an online exploration algorithm
whose competitive ratio is polynomial in $d$ either for the 
general case or for more restricted cases,
like for a planar strongly connected directed graph for example.
We will present our ideas and problems with that.