Title: Exploring an Unknown Graph Efficiently 
Speaker: Gerhard Trippen
HKUST

Date: Friday, April 22, 2005
Time 11-12
Venue: Room 3464, HKUST


Abstract

We study the problem of exploring an unknown, strongly connected
directed graph.
Starting at some node of the graph,
we must visit every edge and every node at least once.
The goal is minimize the number of edge traversals.
We use competitive analysis to evaluate the performance
of exploration algorithms.
It is known that the competitive factor depends
on the deficiency $d$ of the graph,
which is the number of edges that must be added to make the graph Eulerian.
We present the first online exploration algorithm
whose competitive ratio is polynomial in $d$
(it is $O(d^8))$. 

This is joint work with Rudolf Fleischer