%0 Conference Paper %1 Alon2008Many %A Alon, Noga %A Avin, Chen %A Koucky, Michal %A Kozma, Gady %A Lotker, Zvi %A Tuttle, Mark R. %B SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures %C New York, NY, USA %D 2008 %I ACM %K random\_walks networks information-diffusion %P 119--128 %R 10.1145/1378533.1378557 %T Many random walks are faster than one %U http://dx.doi.org/10.1145/1378533.1378557 %X 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. We demonstrate 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 probablistic 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. %@ 978-1-59593-973-9

@inproceedings{Alon2008Many, abstract = {{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. We demonstrate 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 probablistic 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.}}, added-at = {2019-06-10T14:53:09.000+0200}, address = {New York, NY, USA}, author = {Alon, Noga and Avin, Chen and Koucky, Michal and Kozma, Gady and Lotker, Zvi and Tuttle, Mark R.}, biburl = {https://www.bibsonomy.org/bibtex/24ad3a6bd9f3faa9b7aa2262bd02dd3d7/nonancourt}, booktitle = {SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures}, citeulike-article-id = {3768545}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1378533.1378557}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1378533.1378557}, doi = {10.1145/1378533.1378557}, interhash = {4391aa8e1c560db507a9fb1cc5c992b1}, intrahash = {4ad3a6bd9f3faa9b7aa2262bd02dd3d7}, isbn = {978-1-59593-973-9}, keywords = {random\_walks networks information-diffusion}, location = {Munich, Germany}, pages = {119--128}, posted-at = {2008-12-10 16:50:24}, priority = {3}, publisher = {ACM}, timestamp = {2019-07-31T12:36:13.000+0200}, title = {{Many random walks are faster than one}}, url = {http://dx.doi.org/10.1145/1378533.1378557}, year = 2008 }