Many random walks are faster than one
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F08%3A00318535" target="_blank" >RIV/67985840:_____/08:00318535 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Many random walks are faster than one
Original language description
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time-the expected time required to visit every node in a graph at least once-and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. Wedemonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.
Czech name
Mnoho náhodných procházek je rychlejších než jedna
Czech description
Článek se zabývá otázkou doby pokrytí grafu několika nezávislými souběžnými náhodnými procházkami.
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GP201%2F07%2FP276" target="_blank" >GP201/07/P276: Computational and communication complexity of Boolean functions, and derandomization</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 20th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2008
ISBN
978-1-59593-973-9
ISSN
—
e-ISSN
—
Number of pages
10
Pages from-to
—
Publisher name
ACM
Place of publication
Mnichov
Event location
Mnichov
Event date
Jun 14, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—