Analysis of a randomized rendezvous algorithm

AbstractIn 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