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

the techniques could be extended to work for (strongly connected) directed graphs
(e.g. see [ 10 ]). In general, solving rendezvous in directed graphs is more difficult
due to the inability of agents to backtrack and this is one of directions for future re-
search. Another open problem is solving rendezvous in dangerous graphs assuming
the weaker model of communication when there are no whiteboards and the agents
are only provided with a few pebbles.

References

1. R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovász, and C. Rackoff. Random walks, universal
traversal sequences, and the complexity of maze problems. In Proc. of 20th Annual Sympo-
sium on Foundations of Computer Science (FOCS), pp. 218-223, 1979.
2. S. Alpern. Hide and seek games. Seminar, Institut fur Hohere Studien, Wien, July 1976.
3. S. Alpern and S. Gal. The Theory of Search Games and Rendezvous . Kluwer, 2003.
4. E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, A. Labourel. Almost Optimal Asyn-
chronous Rendezvous in Infinite Multidimensional Grids. In Proc. 24th International Sympo-
sium on Distributed Computing (DISC), pp. 297-311, 2010.
5. P. Boldi, B. Codenotti, P. Gemmell, S. Shammah, J. Simon, and S. Vigna. Symmetry breaking
in anonymous networks: Characterizations. In Proc. 4th Israeli Symposium on Theory of

Computing and Systems, pp. 16-26, 1996.
6. P. Boldi and S. Vigna. Fibrations of graphs. Discrete Mathematics, 243(1-3):21-66, 2002.
7. J. Chalopin and S. Das. Rendezvous of Mobile Agents without Agreement on Local Ori-
entation. In Proc. 37th Int. Coll. on Automata, Languages and Programming (ICALP),
pp. 515-526, 2010.
8. J. Chalopin, S. Das, and A. Kosowski. Constructing a Map of an Anonymous Graph: Ap-
plications of Universal Sequences. In Proc. 14th International Conference on Principles of
Distributed Systems (OPODIS), pp. 119-134, 2010.
9. J. Chalopin, S. Das, and N. Santoro. Rendezvous of Mobile Agents in Unknown Graphs with
Faulty Links. In Proc. 21st International Symposium on Distributed Computing (DISC), pp.
108-122, 2007.
10. J. Chalopin, S. Das, and P. Widmayer. Rendezvous of Mobile Agents in Directed Graphs. In
Proc. 24th International Symposium on Distributed Computing (DISC), pp. 282-296, 2010.
11. J. Czyzowicz, A. Labourel, and A. Pelc, How to meet asynchronously (almost) everywhere,
In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 22-30,
2010.
12. J. Czyzowicz, A. Kosowski, A. Pelc. How to meet when you forget: log-space rendezvous in
arbitrary graphs. Distributed Computing 25(2): 165-178, 2012.
13. J. Czyzowicz, A. Kosowski, A. Pelc, Time vs. space trade-offs for rendezvous in trees, In
Proc. 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp.
1-10, 2012.
14. S. Das, P. Flocchini, A. Nayak, and N. Santoro. Effective elections for anonymous mobile
agents. In Proc. 17th Symp. on Algorithms and Computation (ISAAC), pp. 732-743, 2006.
15. S. Das, M. Mihalak, R. Sramek, E. Vicari, P. Widmayer, Rendezvous of mobile agents when
tokens fail anytime, In Proc. 12th Int. Conf. on Principles of Distributed Systems (OPODIS),
pp. 463-480, 2008.
16. A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc. Deterministic rendezvous in graphs, Algo-
rithmica, 46: 69-96, 2006.
17. S. Dobrev, P. Flocchini, G. Prencipe, and N. Santoro. Multiple agents rendezvous in a ring in
spite of a black hole. In Proc. 7th Int. Conf. on Principles of Distributed Systems (OPODIS),
pp. 34-46, 2003.