Campus Event Calendar
Event Entry
What and Who
Exploring an unknown graph efficiently
Rudolf Fleischer
Fudan University, Shanghai, China
Talk
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 22 July 2005
13:30
30 Minutes
46.1 - MPII
024
Saarbrücken
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 to minimize the number of edge traversals.
It is known that the competitive ratio of online algorithms for this problem depends on the deficiency $d$ of the graph, which is the minimum number of edges that must be added to make the graph Eulerian. We present the first deterministic online exploration algorithm whose competitive ratio is polynomial in $d$ (it is O(d^8)).
Contact
Martin Kutz
--email hidden
passcode not visible
logged in users only
Martin Kutz, 07/19/2005 09:41
Martin Kutz, 07/15/2005 11:06 -- Created document.
Martin Kutz, 07/15/2005 11:06 -- Created document.