CS 269S, Spring 2012: Theory Seminar
Bren Hall, Room 1420
April 20, 2012:

How to Meet Asynchronously (Almost) Everywhere

Paweł Pszona

Two independent agents (robots) start in arbitrary nodes of an unknown connected graph (finite or infinite). Agents select their own routes (graph edges they want to take), but their movement along an edge is governed by an adversary. The authors give a deterministic algorithm that guarantees the agents will eventually meet at some point of the graph (not necessarily a vertex). The result is extended to a geometric scenario (on a plane).

(Based on a paper in SODA 2010 by Jurek Czyzowicz, Arnaud Labourel, and Andrzej Pelc.)