Exploring graphs using parallel rotor walks

Add to your list(s) Download to your calendar using vCal

• Dominik Pajak (University of Cambridge)
• Friday 21 November 2014, 14:00-15:00
• Computer Laboratory, Room FW26.

If you have a question about this talk, please contact Dr Thomas Sauerwald.

The most natural deterministic analogue of the random walk in graphs is a process in which walkers are propagated by each node to its neighbours in a round-robin fashion. Such process, called the rotor-router has applications for example in load balancing and rumor spreading. In this talk we will study the speed-up of k-agent rotor-router system with respect to the cover time of a single walk.

We will completely resolve the question of the possible range of speed-ups, showing that its value is between Θ(log k) and Θ(k), for any graph. Both of these bounds are tight. Thus, the proven range of speed-up for the rotor-router corresponds precisely to the conjectured range of speed-up for the random walk. We will also study the speed-up on various graph classes like expanders and multidimensional grids.

Joint work with D. Dereniowski, R. Klasing, A. Kosowski, T. Sauerwald, P. Uznanski.

This talk is part of the Cambridge Algorithms talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Algorithms talks
• Cambridge talks
• Computer Laboratory, Room FW26
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.