University of Cambridge > Talks.cam > Cambridge Algorithms talks > Exploring graphs using parallel rotor walks

Exploring graphs using parallel rotor walks

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity