2026-07-22T16:55:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6989 2024-03-06T10:39:13Z ddc:004 open_access

Multiple Random Walks on Paths and Grids Ivaskovic, Andrej Kosowski, Adrian Pajak, Dominik Sauerwald, Thomas random walks randomized algorithms parallel computing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrej Ivaskovic and Adrian Kosowski and Dominik Pajak and Thomas Sauerwald 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.44 urn:nbn:de:0030-drops-69897 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.44 eng https://creativecommons.org/licenses/by/3.0/legalcode