{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:22:31Z","timestamp":1737091351809,"version":"3.33.0"},"reference-count":17,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4576,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1994,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We initiate a study of random walks on undirected graphs with colored edges. In our model, a sequence of colors is specified before the walk begins, and it dictates the color of edge to be followed at each step. We give tight upper and lower bounds on the expected cover time of a random walk on an undirected graph with colored edges. We show that, in general, graphs with two colors have exponential expected cover time, and graphs with three or more colors have doubly\u2010exponential expected cover time. We also give polynomial bounds on the expected cover time in a number of interesting special cases. We described applications of our results to understanding the dominant eigenvectors of products and weighted averages of stochastic matrices, and to problems on time\u2010inhomogeneous Markov chains. \u00a9 1994 John Wiley &amp; Sons, Inc.<\/jats:p>","DOI":"10.1002\/rsa.3240050204","type":"journal-article","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T20:18:36Z","timestamp":1180729116000},"page":"285-303","source":"Crossref","is-referenced-by-count":5,"title":["Random walks on colored graphs"],"prefix":"10.1002","volume":"5","author":[{"given":"Anne","family":"Condon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diane","family":"Hernek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"R.Aleliunas R.Karp R.Lipton L.Lov\u00e1sz andC.Rackoff Random walks universal traversal sequences and the complexity of maze problems Proc. 20th Symposium on Foundations of Computer Science 218\u2013223(1979).","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"S.Arora C.Lund R.Motwani M.Sudan andM.Szegedy Proof verification and hardness of approximation problems Proc. 33rd Symposium on Foundations of Computer Science 14\u201323(1992).","DOI":"10.1109\/SFCS.1992.267823"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706452"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048273"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/103516.128681"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"A.CondonandR.Lipton On the complexity of space\u2010bounded interactive proofs Proc. 30th Symposium on Foundations of Computer Science 462\u2013467(1989).","DOI":"10.1109\/SFCS.1989.63519"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146599"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4149(74)90001-5"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"N.Immerman Nondeterministic space is closed under complement Proc. Conference on Structure in Complexity Theory 112\u2013115(1988).","DOI":"10.1109\/SCT.1988.5270"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"M.JerrumandA.Sinclair Conductance and the rapid mixing property for Markov chains Proc. 20th ACM Symposium on Theory of Computing 235\u2013244(1988).","DOI":"10.1145\/62212.62234"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"M.Mihail Conductance and convergence of expanders Proc. 30th Symposium on Foundations of Computer Science 526\u2013531(1989).","DOI":"10.1109\/SFCS.1989.63529"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.2307\/2033893"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-32792-4"},{"key":"e_1_2_1_17_2","unstructured":"R.Szelepcs\u00e9nyi The method of forcing for nondeterministic automata Bull. Eur. Assoc. Theor. Comput. Sci. 96\u2013100(October1987)."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.2307\/2034984"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240050204","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240050204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:24:55Z","timestamp":1737062695000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240050204"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,4]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,4]]}},"alternative-id":["10.1002\/rsa.3240050204"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240050204","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"type":"print","value":"1042-9832"},{"type":"electronic","value":"1098-2418"}],"subject":[],"published":{"date-parts":[[1994,4]]}}}