{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T16:53:58Z","timestamp":1763830438088},"reference-count":38,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2011,4,7]],"date-time":"2011-04-07T00:00:00Z","timestamp":1302134400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,7]]},"abstract":"<jats:p>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<jats:italic>cover time<\/jats:italic>\u2013 the expected time required to visit every node in a graph at least once \u2013 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 probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected<jats:italic>s<\/jats:italic>\u2013<jats:italic>t<\/jats:italic>connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.<\/jats:p>","DOI":"10.1017\/s0963548311000125","type":"journal-article","created":{"date-parts":[[2011,4,7]],"date-time":"2011-04-07T10:38:13Z","timestamp":1302172693000},"page":"481-502","source":"Crossref","is-referenced-by-count":58,"title":["Many Random Walks Are Faster Than One"],"prefix":"10.1017","volume":"20","author":[{"given":"NOGA","family":"ALON","sequence":"first","affiliation":[]},{"given":"CHEN","family":"AVIN","sequence":"additional","affiliation":[]},{"given":"MICHAL","family":"KOUCK\u00dd","sequence":"additional","affiliation":[]},{"given":"GADY","family":"KOZMA","sequence":"additional","affiliation":[]},{"given":"ZVI","family":"LOTKER","sequence":"additional","affiliation":[]},{"given":"MARK R.","family":"TUTTLE","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,4,7]]},"reference":[{"key":"S0963548311000125_ref31","first-page":"353","volume-title":"Combinatorics: Paul Erd\u00f6s is Eighty","author":"Lov\u00e1sz","year":"1996"},{"key":"S0963548311000125_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2005.01.002"},{"key":"S0963548311000125_ref9","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/984622.984663","volume-title":"Proc. Third International Symposium on Information Processing in Sensor Networks","author":"Avin","year":"2004"},{"key":"S0963548311000125_ref4","unstructured":"[4] Aldous D. and Fill J. (1999) Reversible Markov chains and random walks on graphs. Unpublished. http:\/\/stat-www.berkeley.edu\/users\/aldous\/RWG\/book.html."},{"key":"S0963548311000125_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2003.08.001"},{"key":"S0963548311000125_ref24","first-page":"19","article-title":"Short random walks on graphs","volume":"1","author":"Feige","year":"1996","journal-title":"SIAM J. Discrete Math."},{"key":"S0963548311000125_ref29","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v5-1022"},{"key":"S0963548311000125_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_55"},{"key":"S0963548311000125_ref22","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060106"},{"key":"S0963548311000125_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/333979.333984"},{"key":"S0963548311000125_ref35","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570741"},{"key":"S0963548311000125_ref27","first-page":"482","volume-title":"Approximations for NP-hard Problems","author":"Jerrum","year":"1997"},{"key":"S0963548311000125_ref28","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003538"},{"key":"S0963548311000125_ref33","unstructured":"[33] Nisan N. , Szemer\u00e9di E. and Wigderson A. (1992) Undirected connectivity in O(log1.5 n) space. In Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 24\u201329."},{"key":"S0963548311000125_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048276"},{"key":"S0963548311000125_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048272"},{"key":"S0963548311000125_ref32","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991894"},{"key":"S0963548311000125_ref15","doi-asserted-by":"crossref","unstructured":"[15] Broder A. , Karlin A. , Raghavan P. and Upfal E. (1989) Trading space for time in undirected s\u2013t connectivity. In Proc. ACM Symp. Theory of Computing, pp. 543\u2013549.","DOI":"10.1145\/73007.73059"},{"key":"S0963548311000125_ref21","first-page":"415","volume-title":"ICALP 1","author":"Els\u00e4sser","year":"2009"},{"key":"S0963548311000125_ref7","first-page":"119","volume-title":"SPAA 2008: Proc. 20th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"Alon","year":"2008"},{"key":"S0963548311000125_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535260"},{"key":"S0963548311000125_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/1132905.1132932"},{"key":"S0963548311000125_ref18","first-page":"399","volume-title":"ICALP 2","author":"Cooper","year":"2009"},{"key":"S0963548311000125_ref12","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1006\/jcss.1997.1471","article-title":"A spectrum of time\u2013space tradeoffs for undirected s\u2013t connectivity","volume":"54","author":"Barnes","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"S0963548311000125_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048273"},{"key":"S0963548311000125_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"S0963548311000125_ref30","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979325247X"},{"key":"S0963548311000125_ref20","first-page":"476","volume-title":"APPROX\u2013RANDOM 2009","author":"Efremenko","year":"2009"},{"key":"S0963548311000125_ref17","first-page":"140","volume-title":"Proc. 14th Annual ACM\u2013SIAM Symposium on Discrete Algorithms: SODA-03","author":"Cooper","year":"2003"},{"key":"S0963548311000125_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/570738.570742"},{"key":"S0963548311000125_ref23","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060406"},{"key":"S0963548311000125_ref36","first-page":"116","volume-title":"RANDOM'98","author":"Wagner","year":"1998"},{"key":"S0963548311000125_ref5","first-page":"218","volume-title":"20th Annual Symposium on Foundations of Computer Science","author":"Aleliunas","year":"1979"},{"key":"S0963548311000125_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2006.104"},{"key":"S0963548311000125_ref16","first-page":"574","volume-title":"Proc. 21st Annual ACM Symposium on Theory of Computing","author":"Chandra","year":"1989"},{"key":"S0963548311000125_ref26","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0078"},{"key":"S0963548311000125_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01047002"},{"key":"S0963548311000125_ref38","first-page":"254","volume-title":"Proc. 22nd Annual ACM Symposium on Theory of Computing","author":"Zuckerman","year":"1990"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,21]],"date-time":"2021-11-21T07:59:43Z","timestamp":1637481583000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000125\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4,7]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["S0963548311000125"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000125","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,4,7]]}}}