Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.44
URN: urn:nbn:de:0030-drops-69897
URL: https://drops.dagstuhl.de/opus/volltexte/2017/6989/
Ivaskovic, Andrej ; Kosowski, Adrian ; Pajak, Dominik ; Sauerwald, Thomas
Multiple Random Walks on Paths and Grids
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{ivaskovic_et_al:LIPIcs:2017:6989,
author = {Andrej Ivaskovic and Adrian Kosowski and Dominik Pajak and Thomas Sauerwald},
title = {{Multiple Random Walks on Paths and Grids}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-028-6},
ISSN = {1868-8969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6989},
URN = {urn:nbn:de:0030-drops-69897},
doi = {10.4230/LIPIcs.STACS.2017.44},
annote = {Keywords: random walks, randomized algorithms, parallel computing}
}
| Keywords: | random walks, randomized algorithms, parallel computing | |
| Seminar: | 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) | |
| Issue date: | 2017 | |
| Date of publication: | 06.03.2017 |
