Bren Hall, Room 1420

April 20, 2012:

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.)