Deterministic Symmetric Rendezvous in Arbitrary Graphs: Overcoming Anonymity, Failures and Uncertainty - Search Theory: A Game Theoretic Perspective - page 165

Chapter 12
Deterministic Symmetric Rendezvous
in Arbitrary Graphs: Overcoming Anonymity,
Failures and Uncertainty
Jérémie Chalopin, Shantanu Das, and Peter Widmayer
Abstract We consider the rendezvous problem of gathering two or more
identical agents that are initially scattered among the nodes of an unknown graph.
We discuss some of the recent results for this problem focusing only on determinis-
tic algorithms for the general case when the graph topology is unknown, the nodes
of the graph may not be uniquely labeled and the agents may not be synchronized
with each other. In this scenario, the objective is to solve rendezvous whenever de-
terministically feasible, while optimizing on the amount of movement by the agents
or the memory required (for the nodes or the agents) in the worst case. Further we
also investigate some special scenarios such as (i) when the graph contains some
dangerous nodes or, (ii) when there is no consistent ordering on the edges of a node.
We present positive results, complexity analysis and some general techniques for
dealing with such worst case scenarios for the symmetric rendezvous problem.
12.1 Introduction
The problem of rendezvous requires two or more entities (called agents ) located in
distinct vertices of a graph, to meet at one vertex of the graph. This problem oc-
curs in many natural contexts [ 3 ] and requires different strategies depending on the
scenario and the particular objective. In the original definition of the problem [ 2 ],