{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:53:24Z","timestamp":1725558804930},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642140303"},{"type":"electronic","value":"9783642140310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14031-0_16","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T09:50:06Z","timestamp":1277718606000},"page":"130-139","source":"Crossref","is-referenced-by-count":7,"title":["The Cover Time of Deterministic Random Walks"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Sauerwald","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Aldous, D.: On the time taken by random walks on finite groups to visit every state. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete, 361\u2013374 (1983)","DOI":"10.1007\/BF00535260"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R., Lipton, R., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201979), pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-642-04355-0_44","volume-title":"Distributed Computing","author":"E. Bampas","year":"2009","unstructured":"Bampas, E., Gasieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A.: Euler tour lock-in problem in the rotor-router model. In: Keidar, I. (ed.) DISC 2009. LNCS, vol.\u00a05805, pp. 423\u2013435. Springer, Heidelberg (2009)"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01048273","volume":"2","author":"A. Broder","year":"1989","unstructured":"Broder, A., Karlin, A.: Bounds on the cover time. Journal of Theoretical Probability\u00a02(1), 101\u2013120 (1989)","journal-title":"Journal of Theoretical Probability"},{"issue":"4","key":"16_CR5","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/BF01270385","volume":"6","author":"A. Chandra","year":"1997","unstructured":"Chandra, A., Raghavan, P., Ruzzo, W., Smolensky, R., Tiwari, P.: The electrical resistance of a graph captures its commute and cover times. Computational Complexity\u00a06(4), 312\u2013340 (1997)","journal-title":"Computational Complexity"},{"issue":"4","key":"16_CR6","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/S0895480103428478","volume":"18","author":"C. Cooper","year":"2005","unstructured":"Cooper, C., Frieze, A.: The cover time of random regular graphs. SIAM Journal of Discrete Mathematics\u00a018(4), 728\u2013740 (2005)","journal-title":"SIAM Journal of Discrete Mathematics"},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1002\/rsa.20201","volume":"32","author":"C. Cooper","year":"2008","unstructured":"Cooper, C., Frieze, A.: The cover time of the giant component of a random graph. Random Structures & Algorithms\u00a032(4), 401\u2013439 (2008)","journal-title":"Random Structures & Algorithms"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"Cooper, C., Frieze, A.: The cover time of random geometric graphs. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201909) , pp. 48\u201357 (2009)","DOI":"10.1137\/1.9781611973068.6"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-02930-1_34","volume-title":"Automata, Languages and Programming","author":"C. Cooper","year":"2009","unstructured":"Cooper, C., Ilcinkas, D., Klasing, R., Kosowski, A.: Derandomizing random walks in undirected graphs using locally fair exploration strategies. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 411\u2013422. Springer, Heidelberg (2009)"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1017\/S0963548306007565","volume":"15","author":"J. Cooper","year":"2006","unstructured":"Cooper, J., Spencer, J.: Simulating a random walk with constant error. Combinatorics, Probability & Computing\u00a015, 815\u2013822 (2006)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"8","key":"16_CR11","doi-asserted-by":"publisher","first-page":"2072","DOI":"10.1016\/j.ejc.2007.04.018","volume":"28","author":"J. Cooper","year":"2007","unstructured":"Cooper, J., Doerr, B., Spencer, J., Tardos, G.: Deterministic random walks on the integers. European Journal of Combinatorics\u00a028(8), 2072\u20132090 (2007)","journal-title":"European Journal of Combinatorics"},{"key":"16_CR12","unstructured":"Cooper, J., Doerr, B., Friedrich, T., Spencer, J.: Deterministic random walks on regular trees. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201908), pp. 766\u2013772 (2008)"},{"issue":"3","key":"16_CR13","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1214\/aoap\/1177005359","volume":"3","author":"P. Diaconis","year":"1993","unstructured":"Diaconis, P., Saloff-Coste, L.: Comparison theorems for reversible Markov chains. Annals of Applied Probability\u00a03(3), 696\u2013730 (1993)","journal-title":"Annals of Applied Probability"},{"issue":"1-2","key":"16_CR14","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1017\/S0963548308009589","volume":"18","author":"B. Doerr","year":"2009","unstructured":"Doerr, B., Friedrich, T.: Deterministic random walks on the two-dimensional grid. Combinatorics, Probability & Computing\u00a018(1-2), 123\u2013144 (2009)","journal-title":"Combinatorics, Probability & Computing"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201908), pp. 773\u2013781 (2008)","DOI":"10.1145\/1963190.2025379"},{"issue":"4","key":"16_CR16","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1137\/S0895480102408341","volume":"16","author":"I. Dumitriu","year":"2003","unstructured":"Dumitriu, I., Tetali, P., Winkler, P.: On playing golf with two balls. SIAM J. Discrete Math.\u00a016(4), 604\u2013615 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"16_CR17","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1002\/rsa.3240060406","volume":"6","author":"U. Feige","year":"1995","unstructured":"Feige, U.: A tight lower bound for the cover time of random walks on graphs. Random Structures & Algorithms\u00a06(4), 433\u2013438 (1995)","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"16_CR18","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01270386","volume":"6","author":"U. Feige","year":"1997","unstructured":"Feige, U.: Collecting coupons on trees, and the cover time of random walks. Computational Complexity\u00a06(4), 341\u2013356 (1997)","journal-title":"Computational Complexity"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Friedrich, T., Sauerwald, T.: Near-perfect load balancing by randomized rounding. In: 41st Annual ACM Symposium on Theory Progarmming (STOC\u201909), pp. 121\u2013130 (2009)","DOI":"10.1145\/1536414.1536433"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"Friedrich, T., Gairing, M., Sauerwald, T.: Quasirandom load balancing. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201910), pp. 1620\u20131629 (2010)","DOI":"10.1137\/1.9781611973075.132"},{"key":"16_CR21","unstructured":"Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201907) , pp. 585\u2013594 (2007)"},{"key":"16_CR22","unstructured":"Holroyd, A.E., Propp, J.: Rotor walks and markov chains (2009), arXiv:0904.4507"},{"issue":"2-3","key":"16_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0004-3702(90)90054-4","volume":"42","author":"R.E. Korf","year":"1990","unstructured":"Korf, R.E.: Real-time heuristic search. Artif. Intell.\u00a042(2-3), 189\u2013211 (1990)","journal-title":"Artif. Intell."},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1512\/iumj.2008.57.3022","volume":"57","author":"L. Levine","year":"2008","unstructured":"Levine, L., Peres, Y.: Spherical asymptotics for the rotor-router model in \u2124 d . Indiana Univ. Math. J.\u00a057, 431\u2013450 (2008)","journal-title":"Indiana Univ. Math. J."},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11118-008-9104-6","volume":"30","author":"L. Levine","year":"2009","unstructured":"Levine, L., Peres, Y.: Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile. Potential Analysis\u00a030, 1\u201327 (2009)","journal-title":"Potential Analysis"},{"key":"16_CR26","first-page":"1","volume":"2","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Random walks on graphs: A survey. Combinatorics, Paul Erd\u00f6s is Eighty\u00a02, 1\u201346 (1993)","journal-title":"Combinatorics, Paul Erd\u00f6s is Eighty"},{"issue":"1","key":"16_CR27","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/rsa.3240050116","volume":"5","author":"J.L. Palacios","year":"1994","unstructured":"Palacios, J.L.: Expected hitting and cover times of random walks on some special graphs. Random Structures & Algorithms\u00a05(1), 173\u2013182 (1994)","journal-title":"Random Structures & Algorithms"},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"5079","DOI":"10.1103\/PhysRevLett.77.5079","volume":"77","author":"V.B. Priezzhev","year":"1996","unstructured":"Priezzhev, V.B., Dhar, D., Dhar, A., Krishnamurthy, S.: Eulerian walkers as a model of self-organized criticality. Phys. Rev. Lett.\u00a077, 5079\u20135082 (1996)","journal-title":"Phys. Rev. Lett."},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of Markov chains and the analysis of iterative load balancing schemes. In: 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201998), pp. 694\u2013705 (1998)","DOI":"10.1109\/SFCS.1998.743520"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4) (2008)","DOI":"10.1145\/1391289.1391291"},{"issue":"1","key":"16_CR31","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0020-0190(90)90173-U","volume":"35","author":"R. Rubinfeld","year":"1990","unstructured":"Rubinfeld, R.: The cover time of a regular expander is $\\mathcal{O}(n \\log n)$ . Inf. Process. Lett.\u00a035(1), 49\u201351 (1990)","journal-title":"Inf. Process. Lett."},{"key":"16_CR32","unstructured":"Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Smell as a computational resource - a lesson we can learn from the ant. In: Israeli Symposium on Theory of Computing and Systems (ISTCS \u201996), pp. 219\u2013230 (1996)"},{"issue":"5","key":"16_CR33","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1109\/70.795795","volume":"15","author":"I.A. Wagner","year":"1999","unstructured":"Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Distributed covering by ant-robots using evaporating traces. IEEE Transactions on Robotics and Automation\u00a015(5), 918\u2013933 (1999)","journal-title":"IEEE Transactions on Robotics and Automation"},{"issue":"3","key":"16_CR34","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00453-003-1030-9","volume":"37","author":"V. Yanovski","year":"2003","unstructured":"Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica\u00a037(3), 165\u2013186 (2003)","journal-title":"Algorithmica"},{"issue":"6","key":"16_CR35","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0020-0190(91)90091-U","volume":"38","author":"D. Zuckerman","year":"1991","unstructured":"Zuckerman, D.: On the time to traverse all edges of a graph. Inf. Process. Lett.\u00a038(6), 335\u2013337 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"16_CR36","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1137\/0405007","volume":"5","author":"D. Zuckerman","year":"1992","unstructured":"Zuckerman, D.: A technique for lower bounding the cover time. SIAM Journal on Discrete Mathematics\u00a05(1), 81\u201387 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14031-0_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T19:37:56Z","timestamp":1685648276000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14031-0_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642140303","9783642140310"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14031-0_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}