Multiple Random Walks on Paths and Grids - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

Multiple Random Walks on Paths and Grids

(1) , (2) , (3) , (1)
1
2
3

Abstract

We derive several new results on multiple random walks on "low dimensional" graphs. First, inspired by an example of a weighted random walk on a path of three vertices given by Efremenko and Reingold, we prove the following dichotomy: as the path length n tends to infinity, we have a super-linear speed-up w.r.t. the cover time if and only if the number of walks k is equal to 2. An important ingredient of our proofs is the use of a continuous-time analogue of multiple random walks, which might be of independent interest. Finally, we also present the first tight bounds on the speed-up of the cover time for any d-dimensional grid with d >= 2 being an arbitrary constant, and reveal a sharp transition between linear and logarithmic speed-up.
Fichier principal
Vignette du fichier
LIPIcs-STACS-2017-44.pdf (510.98 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01669223 , version 1 (07-02-2018)

Identifiers

Cite

Andrej Ivaskovic, Adrian Kosowski, Dominik Pająk, Thomas Sauerwald. Multiple Random Walks on Paths and Grids . STACS 2017 - 34th Symposium on Theoretical Aspects of Computer Science, Mar 2017, Hannover, Germany. pp.1-14, ⟨10.4230/LIPIcs.STACS.2017.44⟩. ⟨hal-01669223⟩
279 View
118 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More