Analysis of a randomized rendezvous algorithm

In this paper we propose and analyze a randomized algorithm to get rendezvous between neighbours in an anonymous graph. We examine in particular the probability to obtain at least one rendezvous and the expected number of rendezvous. We study the rendezvous number distribution in the cases of chain graphs, rings, and complete graphs. The last part is devoted to the efficiency of the proposed algorithm.

Authors

• Yves Métivier
• Nasser Saheb
• Akka Zemmari

Keywords

• Randomized algorithm
• Analysis of algorithm
• Efficiency
• Graph
• Rendezvous