The power of two choices for random walks
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
We apply the power-of-two-choices paradigm to a random walk on a graph:
rather than moving to a uniform random neighbour at each step, a controller is
allowed to choose from two independent uniform random neighbours. We prove that
this allows the controller to significantly accelerate the hitting and cover
times in several natural graph classes. In particular, we show that the cover
time becomes linear in the number
Description
Keywords
Journal Title
Conference Name
Journal ISSN
1469-2163