On asynchronous rendezvous in general graphs

Evangelos Bampas (1) , Lélia Blin (2, 3) , Jurek Czyzowicz (4) , David Ilcinkas (5, 6) , Arnaud Labourel (1) , Maria Potop-Butucaru (3) , Sébastien Tixeuil (3)

1 LIS - Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon)
2 UEVE - Université d'Évry-Val-d'Essonne
3 NPA - Networks and Performance Analysis
4 DII - Département d'Informatique et d'Ingénierie
5 LaBRI - Laboratoire Bordelais de Recherche en Informatique
6 CNRS - Centre National de la Recherche Scientifique

A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced.

Domains: Data Structures and Algorithms [cs.DS]

Evangelos Bampas, Lélia Blin, Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel, et al.. On asynchronous rendezvous in general graphs. Theoretical Computer Science, 2019, 753, pp.80-90. ⟨10.1016/j.tcs.2018.06.045⟩. ⟨hal-01900843⟩