{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:48:37Z","timestamp":1742914117573,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029295"},{"type":"electronic","value":"9783642029301"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02930-1_34","type":"book-chapter","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T15:05:04Z","timestamp":1246547104000},"page":"411-422","source":"Crossref","is-referenced-by-count":4,"title":["Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies"],"prefix":"10.1007","author":[{"given":"Colin","family":"Cooper","sequence":"first","affiliation":[]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[]},{"given":"Adrian","family":"Kosowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"34_CR1","unstructured":"Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs (2001), http:\/\/stat-www.berkeley.edu\/users\/aldous\/RWG\/book.html"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal sequences and the complexity of maze problems. In: Proceedings of the 20th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 1979), pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"issue":"1","key":"34_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: Exploring and mapping directed graphs. Information and Computation\u00a0176(1), 1\u201321 (2002)","journal-title":"Information and Computation"},{"issue":"2","key":"34_CR4","doi-asserted-by":"publisher","first-page":"157","DOI":"10.7155\/jgaa.00049","volume":"6","author":"S.N. Bhatt","year":"2002","unstructured":"Bhatt, S.N., Even, S., Greenberg, D.S., Tayar, R.: Traversing directed eulerian mazes. Journal of Graph Algorithms and Applications\u00a06(2), 157\u2013173 (2002)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"34_CR5","unstructured":"Cooper, J., Doerr, B., Friedrich, T., Spencer, J.: Deterministic Random Walks on Regular Trees. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 766\u2013772 (2008)"},{"issue":"3","key":"34_CR6","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8","volume":"32","author":"X. Deng","year":"1999","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an Unknown Graph. Journal of Graph Theory\u00a032(3), 265\u2013297 (1999)","journal-title":"Journal of Graph Theory"},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"Doerr, B., Friedrich, T.: Deterministic Random Walks on the Two-Dimensional Grid. Combinatorics, Probability and Computing (to appear, 2009), doi:10.1017\/S0963548308009589","DOI":"10.1017\/S0963548308009589"},{"issue":"2-3","key":"34_CR8","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2005.07.014","volume":"345","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoretical Computer Science\u00a0345(2-3), 331\u2013344 (2005)","journal-title":"Theoretical Computer Science"},{"key":"34_CR9","unstructured":"G\u0105sieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 585\u2013594 (2007)"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Hemmerling, A.: Labyrinth Problems: Labyrinth-Searching Abilities of Automata. Teubner-Texte zur Mathematik\u00a0114 (1989)","DOI":"10.1007\/978-3-322-94560-0"},{"issue":"1","key":"34_CR11","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.tcs.2008.10.020","volume":"410","author":"S. Ikeda","year":"2009","unstructured":"Ikeda, S., Kubo, I., Yamashita, M.: The hitting and cover times of random walks on finite graphs using local degree information. Theoretical Computer Science\u00a0410(1), 94\u2013100 (2009)","journal-title":"Theoretical Computer Science"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1109\/SFCS.2000.892134","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000)","author":"J. Kahn","year":"2000","unstructured":"Kahn, J., Kim, J.H., Lov\u00e1sz, L., Vu, V.H.: The cover time, the blanket time, and the Matthews bound. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 467\u2013475. IEEE, Los Alamitos (2000)"},{"key":"34_CR13","unstructured":"Koenig, S.: Complexity of Edge Counting. In: Goal-Directed Acting with Incomplete Information. Technical Report CMU-CS-97-199, Carnegie Mellon University (1997)"},{"key":"34_CR14","unstructured":"Koenig, S., Simmons, R.G.: Easy and Hard Testbeds for Real-Time Search Algorithms. In: Proceedings of the National Conference on Artificial Intelligence, pp. 279\u2013285 (1996)"},{"issue":"4","key":"34_CR15","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1016\/S0022-0000(02)00023-5","volume":"65","author":"M. Kouck\u00fd","year":"2002","unstructured":"Kouck\u00fd, M.: Universal traversal sequences with backtracking. Journal of Computer and System Sciences\u00a065(4), 717\u2013726 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR16","first-page":"353","volume":"2","author":"L. Lov\u00e1sz","year":"1996","unstructured":"Lov\u00e1sz, L.: Random walks on graphs: A survey. Bolyai Society Mathematical Studies\u00a02, 353\u2013397 (1996)","journal-title":"Bolyai Society Mathematical Studies"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"Saks, M.E.: Randomization and derandomization in space-bounded computation. In: Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pp. 128\u2013149 (1996)","DOI":"10.1109\/CCC.1996.507676"},{"key":"34_CR19","unstructured":"Wagner, I.A., Lindenbaum, M., Bruckstein, A.M.: Smell as a Computational Resource \u2014 a Lesson We Can Learn from the Ants. In: Proceedings of Fourth Israeli Symposium on Theory of Computing and Systems (ISTCS 1996), pp. 219\u2013230 (1996)"},{"issue":"5","key":"34_CR20","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":"4","key":"34_CR21","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1002\/(SICI)1098-2418(199612)9:4<403::AID-RSA4>3.0.CO;2-0","volume":"9","author":"P. Winkler","year":"1996","unstructured":"Winkler, P., Zuckerman, D.: Multiple cover time. Random Structures and Algorithms\u00a09(4), 403\u2013411 (1996)","journal-title":"Random Structures and Algorithms"},{"key":"34_CR22","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, 165\u2013186 (2003)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02930-1_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T16:44:53Z","timestamp":1739205893000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02930-1_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029295","9783642029301"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02930-1_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}