{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:00:22Z","timestamp":1725534022996},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642024269"},{"type":"electronic","value":"9783642024276"}],"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-02427-6_18","type":"book-chapter","created":{"date-parts":[[2009,6,24]],"date-time":"2009-06-24T15:44:07Z","timestamp":1245858247000},"page":"95-106","source":"Crossref","is-referenced-by-count":4,"title":["Random Walks on Random Graphs"],"prefix":"10.1007","author":[{"given":"Colin","family":"Cooper","sequence":"first","affiliation":[]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di: Deterministic simulation in LOGSPACE. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 132\u2013140 (1987)","DOI":"10.1145\/28395.28410"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0403039","volume":"3","author":"D. Aldous","year":"1990","unstructured":"Aldous, D.: The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees. SIAM Journal on Discrete Mathematics\u00a03, 450\u2013465 (1990)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"18_CR3","unstructured":"Aldous, D., Fill, J.: Reversible Markov Chains and Random Walks on Graphs, http:\/\/stat-www.berkeley.edu\/pub\/users\/aldous\/RWG\/book.html"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. In: Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica\u00a06, 83\u201396 (1986)","journal-title":"Combinatorica"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2007.02.065","volume":"380","author":"C. Avin","year":"2007","unstructured":"Avin, C., Ercal, G.: On the cover time and mixing time of random geometric graphs. Theoretical Computer Science\u00a0380, 2\u201322 (2007)","journal-title":"Theoretical Computer Science"},{"key":"18_CR7","unstructured":"Alon, N., Avin, C., Kouch\u00fd, M., Kozma, G., Lotker, Z., Tuttle, M.: Many random walks are faster then one (to appear)"},{"key":"18_CR8","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A., Albert, R.: Emergence of scaling in random networks. Science\u00a0286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"18_CR9","unstructured":"Bourassa, V., Holt, F.: SWAN: Small-world wide area networks. In: Proceedings of International Conference on Advances in Infrastructure (SSGRR 2003w), L\u2019Aquila, Italy, paper # 64 (2003), http:\/\/www.panthesis.com\/content\/swan_white_paper.pdf"},{"key":"18_CR10","doi-asserted-by":"crossref","unstructured":"Broder, A.Z.: Generating Random Spanning Trees. In: Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 442\u2013447 (1989)","DOI":"10.1109\/SFCS.1989.63516"},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"Broder, A., Karlin, A., Raghavan, A., Upfal, E.: Trading space for time in undirected s-t connectivity. In: Proc. ACM Symp. Theory of Computing, pp. 543\u2013549 (1989)","DOI":"10.1145\/73007.73059"},{"key":"18_CR12","unstructured":"Bush, S.F., Li, Y.: Network Characteristics of Carbon nanotubes: A Graph Eigenspectrum Approach and Tool Using Mathematica, GE Technical Information Series Report: 2006GRC023"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1080\/15427951.2004.10129078","volume":"1","author":"C. Cooper","year":"2003","unstructured":"Cooper, C., Frieze, A.: Crawling on simple models of web-graphs. Internet Mathematics\u00a01, 57\u201390 (2003)","journal-title":"Internet Mathematics"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1137\/S0895480103428478","volume":"18","author":"C. Cooper","year":"2005","unstructured":"Cooper, C., Frieze, A.M.: The cover time of random regular graphs. SIAM Journal on Discrete Mathematics\u00a018, 728\u2013740 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"18_CR15","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.jctb.2006.05.007","volume":"97","author":"C. Cooper","year":"2007","unstructured":"Cooper, C., Frieze, A.M.: The cover time of the preferential attachment graph. Journal of Combinatorial Theory Series B\u00a097(2), 269\u2013290 (2007)","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20151","volume":"30","author":"C. Cooper","year":"2007","unstructured":"Cooper, C., Frieze, A.M.: The cover time of sparse random graphs. Random Structures and Algorithms\u00a030, 1\u201316 (2007)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1002\/rsa.20201","volume":"32","author":"C. Cooper","year":"2008","unstructured":"Cooper, C., Frieze, A.M.: The cover time of the giant component of a random graph. Random Structures and Algoritms\u00a032, 401\u2013439 (2008)","journal-title":"Random Structures and Algoritms"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-540-74208-1_31","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C. Cooper","year":"2007","unstructured":"Cooper, C., Frieze, A.M.: The cover time of random digraphs. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol.\u00a04627, pp. 422\u2013435. Springer, Heidelberg (2007)"},{"key":"18_CR19","unstructured":"Cooper, C., Frieze, A.M.: The cover time of random geometric graphs (to appear)"},{"key":"18_CR20","unstructured":"Cooper, C., Frieze, A., Radzik, T.: Multiple random walks in random regular graphs (to appear)"},{"key":"18_CR21","unstructured":"Cooper, C., Klasing, R., Radzik, T.: A randomized algorithm for the joining protocol in dynamic distributed networks. J. Theoretical Computer Science (to appear); also published as INRIA report RR-5376 and CNRS report I3S\/RR-2004-39-FR"},{"key":"18_CR22","unstructured":"Doyle, P.G., Snell, J.: Random Walks and Electric Networks, Mathematical Association of America (1984), http:\/\/xxx.lanl.gov\/abs\/math.PR\/0001057"},{"key":"18_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01582563","volume":"64","author":"M.E. Dyer","year":"1994","unstructured":"Dyer, M.E., Frieze, A.M.: Random walks, totally unimodular matrices and a randomised dual simplex algorithm. Mathematical Programming\u00a064, 1\u201316 (1994)","journal-title":"Mathematical Programming"},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1002\/rsa.3240060106","volume":"6","author":"U. Feige","year":"1995","unstructured":"Feige, U.: A tight upper bound for the cover time of random walks on graphs. Random Structures and Algorithms\u00a06, 51\u201354 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR25","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 and Algorithms\u00a06, 433\u2013438 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR26","unstructured":"http:\/\/www.math.cmu.edu\/~af1p\/Mixingbook.pdf"},{"key":"18_CR27","doi-asserted-by":"publisher","first-page":"1790","DOI":"10.1137\/S0097539700366103","volume":"30","author":"A.M. Frieze","year":"2001","unstructured":"Frieze, A.M.: Edge disjoint paths in expander graphs. SIAM Journal on Computing\u00a030, 1790\u20131801 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR28","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bulletin of the American Mathematical Society\u00a043, 439\u2013561 (2006)","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"2","key":"18_CR29","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1002\/rsa.3240070205","volume":"7","author":"M.R. Jerrum","year":"1995","unstructured":"Jerrum, M.R.: A very simple algorithm for estimating the number of k-colourings of a low-degree graph. Random Structures and Algorithms\u00a07(2), 157\u2013165 (1995)","journal-title":"Random Structures and Algorithms"},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Jerrum, M.R.: Counting, sampling and integrating: algorithms and complexity. Lectures in Mathematics\u2013ETH Z\u00fcrich, Birkh\u00e4user (2003)","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"18_CR31","unstructured":"Jerrum, M., Sinclair, A.: The Markov chain Monte Carlo method: an approach to approximate counting and integration. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, pp. 482\u2013520. PWS (1996)"},{"key":"18_CR32","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1017\/S0963548398003538","volume":"7","author":"J. Jonasson","year":"1998","unstructured":"Jonasson, J.: On the cover time of random walks on random graphs. Combinatorics, Probability and Computing\u00a07, 265\u2013279 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"key":"18_CR33","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF01458701","volume":"84","author":"G. Polya","year":"1921","unstructured":"Polya, G.: \u00dcber eine Aufgabe der Wahrscheinlichkeitstheorie betreffend die Irrfahrt im Strassennetz. Mathematische Annalen\u00a084, 149\u2013160 (1921)","journal-title":"Mathematische Annalen"},{"key":"18_CR34","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, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"}],"container-title":["Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering","Nano-Net"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02427-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:12:35Z","timestamp":1558404755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02427-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642024269","9783642024276"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02427-6_18","relation":{},"ISSN":["1867-8211","1867-822X"],"issn-type":[{"type":"print","value":"1867-8211"},{"type":"electronic","value":"1867-822X"}],"subject":[],"published":{"date-parts":[[2009]]}}}