Campus Event Calendar
Event Entry
What and Who
Exploration and rendezvous problems in undirected graphs
Andrzej Pelc
University of Quebec, Canada
Lecture
AG 1, AG 2, AG 3, AG 4
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 19 November 2003
13:30
-- Not specified --
46.1 - MPII
024
Saarbrücken
Abstract
A robot (mobile agent) has to explore an unknown or partially known connected undirected graph. Every edge must be traversed and exploration has to be completed as fast as possible. We compare the performance of deterministic exploration algorithms that do not know the graph (or know it only partially) to that of an optimal algorithm having full knowledge of the graph.
We seek exploration algorithms for which this worst-case ratio is the smallest. We consider scenarios where the robot has no knowledge of the graph and when it has an unoriented map (isomorphic copy) of it.
A problem related to graph exploration is rendezvous in graphs. Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios:
- simultaneous startup, when both agents start executing the algorithm at the same time, and
- arbitrary startup, when starting times of the agents are arbitrarily decided by the adversary.
Contact
Dariusz Kowalski
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Algorithms, Agents, Graphs
Dariusz Kowalski, 10/24/2003 12:56
Uwe Brahm, 10/23/2003 16:03
Dariusz Kowalski, 10/22/2003 15:03 -- Created document.
Uwe Brahm, 10/23/2003 16:03
Dariusz Kowalski, 10/22/2003 15:03 -- Created document.