BAD'16 Poster

Bristol Algorithms Days 2016
Workshop on Efficient Algorithms and Lower Bounds

2 - 3 February 2016

  •    •    •  

Multiple Random Walks

Thomas Sauerwald

In this talk we will consider multiple random walks that run independently and in parallel on an undirected graph. Following Alon, Avin, Kouck√Ĺ, Kozma, Lotker and Tuttle (2008), we will study the speed-up defined as the ratio of the cover time of a single random walk to the cover time of k independent random walks. We will investigate the speed-up on various network topologies and outline potential applications in randomised algorithms.


  The University of Bristol   EPSRC