{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T16:39:42Z","timestamp":1780331982524,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,12,1]],"date-time":"1996-12-01T00:00:00Z","timestamp":849398400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1996,12]]},"DOI":"10.1007\/bf01270385","type":"journal-article","created":{"date-parts":[[2005,3,24]],"date-time":"2005-03-24T04:42:18Z","timestamp":1111639338000},"page":"312-340","source":"Crossref","is-referenced-by-count":237,"title":["The electrical resistance of a graph captures its commute and cover times"],"prefix":"10.1007","volume":"6","author":[{"given":"Ashok K.","family":"Chandra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walter L.","family":"Ruzzo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roman","family":"Smolensky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasoon","family":"Tiwari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"CR1","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF00535260","volume":"62","author":"D. J. Aldous","year":"1983","unstructured":"D. J. Aldous, On the time taken by random walks on finite groups to visit every state.Z. Wahrsch. Verw. Gebiete 62(3) (1983), 361?374.","journal-title":"Z. Wahrsch. Verw. Gebiete"},{"key":"CR2","volume-title":"Reversible Markov chains and random walks on graphs","author":"D. J. Aldous","year":"1993","unstructured":"D. J. Aldous,Reversible Markov chains and random walks on graphs. 1993. Draft, University of California, Berkeley."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lov\u00e1sz, and C. W. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems. InProc. 20th Ann. IEEE Symp. Found. Comput. Sci., San Juan, Puerto Rico, 1979, IEEE, 218?223.","DOI":"10.1109\/SFCS.1979.34"},{"issue":"2","key":"CR4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"N. Alon, Eigenvalues and expanders.Combinatorica 6(2) (1986), 83?96.","journal-title":"Combinatorica"},{"issue":"1","key":"CR5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1137\/S0895480194264988","volume":"9","author":"G. Barnes","year":"1996","unstructured":"G. Barnes andU. Feige, Short random walks on graphs.SIAM J. Disc. Math. 9(1) (1996), 19?28.","journal-title":"SIAM J. Disc. Math."},{"issue":"3","key":"CR6","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1137\/0218038","volume":"18","author":"A. Borodin","year":"1989","unstructured":"A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, andM. Tompa, Two applications of inductive counting for complementation problems.SIAM J. Comput. 18(3) (1989), 559?578. See also18(6): 1283, December 1989.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"CR7","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/0022-0000(92)90046-L","volume":"45","author":"A. Borodin","year":"1992","unstructured":"A. Borodin, W. L. Ruzzo, andM. Tompa, Lower bounds on the length of universal traversal sequences.J. Comput. System Sci. 45(2) (1992), 180?203.","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"CR8","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01048273","volume":"2","author":"A. Z. Broder","year":"1989","unstructured":"A. Z. Broder andA. R. Karlin, Bounds on the cover time.J. Theoret. Probability 2(1) (1989), 101?120.","journal-title":"J. Theoret. Probability"},{"issue":"2","key":"CR9","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1137\/S0097539790190144","volume":"23","author":"A. Z. Broder","year":"1994","unstructured":"A. Z. Broder, A. R. Karlin, P. Raghavan, andE. Upfal, Trading space for time in undirecteds-t connectivity.SIAM J. Comput. 23(2) (1994), 324?334.","journal-title":"SIAM J. Comput."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, P. Raghavan, W. L. Ruzzo, R. Smolensky, and P. Tiwari, The electrical resistance of a graph captures its commute and cover times. InProc. Twenty-first Ann. ACM Symp. Theor. Comput., Seattle, WA, 1989, 574?586.","DOI":"10.1145\/73007.73062"},{"issue":"4","key":"CR11","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1214\/aop\/1176991158","volume":"17","author":"J. T. Cox","year":"1989","unstructured":"J. T. Cox, Coalescing random walks and voter model consensus times on the torus inZd.The Annals of Probability 17(4) (1989), 1333?1366.","journal-title":"The Annals of Probability"},{"key":"CR12","unstructured":"P. G. Doyle, Personal communication, 1988."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"P. G. Doyle and J. L. Snell,Random Walks and Electrical Networks. The Mathematical Association of America, 1984.","DOI":"10.5948\/UPO9781614440222"},{"issue":"1","key":"CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M. Dyer","year":"1991","unstructured":"M. Dyer, A. M. Frieze, andR. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies.J. Assoc. Comput. Mach. 38(1) (1991), 1?17.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"U. Feige, A randomized time-space tradeoff of $$\\tilde O(m\\hat R)$$ for USTCON. InProc. 34th Ann. Symp. Found. Comput. Sci., Palo Alto, CA, 1993, IEEE, 238?246.","DOI":"10.1109\/SFCS.1993.366863"},{"key":"CR16","unstructured":"J. N. Franklin,Matrix Theory. Prentice-Hall, 1968."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"J. Friedman and N. J. Pippenger, Expanding graphs contain all small trees.Combinatorica (1987), 71?76.","DOI":"10.1007\/BF02579202"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-4149(74)90001-5","volume":"2","author":"F. G\u00f6bel","year":"1974","unstructured":"F. G\u00f6bel andA. A. Jagers, Random walks on graphs.Stochastic Processes and their Applications 2 (1974), 311?336.","journal-title":"Stochastic Processes and their Applications"},{"issue":"6","key":"CR19","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. Jerrum","year":"1989","unstructured":"M. Jerrum andA. Sinclair, Approximating the permanent.SIAM J. Comput. 18(6) (1989), 1149?1178.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"CR20","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01048274","volume":"2","author":"J. D. Kahn","year":"1989","unstructured":"J. D. Kahn, N. Linial, N. Nisan, andM. E. Saks, On the cover time of random walks on graphs.J. Theoret. Probability 2(1) (1989), 121?128.","journal-title":"J. Theoret. Probability"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0024-3795(81)90003-3","volume":"38","author":"H. J. Landau","year":"1981","unstructured":"H. J. Landau andA. M. Odlyzko, Bounds for eigenvalues of certain stochastic matrices.Linear Algebra and Its Applications 38 (1981), 5?15.","journal-title":"Linear Algebra and Its Applications"},{"issue":"1","key":"CR22","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1214\/aop\/1176991894","volume":"16","author":"P. Matthews","year":"1988","unstructured":"P. Matthews, Covering problems for Brownian motion on spheres.The Annals of Probability 16(1) (1988), 189?199.","journal-title":"The Annals of Probability"},{"key":"CR23","unstructured":"J. C. Maxwell,A Treatise on Electricity and Magnetism. Clarendon, 1918."},{"issue":"3","key":"CR24","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF02125897","volume":"9","author":"D. Peleg","year":"1989","unstructured":"D. Peleg andE. Upfal, Constructing disjoint paths on expander graphs.Combinatorica 9(3) (1989), 289?313.","journal-title":"Combinatorica"},{"key":"CR25","unstructured":"S. M. Ross,Introduction to Probability Models. Academic Press, fourth edition, 1989."},{"issue":"1","key":"CR26","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0020-0190(90)90173-U","volume":"35","author":"R. Rubinfeld","year":"1990","unstructured":"R. Rubinfeld, The cover time of a regular expander isO(nlogn).Inform. Process. Lett. 35(1) (1990), 49?51.","journal-title":"Inform. Process. Lett."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/qam\/42958","volume":"9","author":"J. L. Synge","year":"1951","unstructured":"J. L. Synge, The fundamental theorem of electrical networks.Quarterly of Applied Math. 9 (1951), 113?127.","journal-title":"Quarterly of Applied Math."},{"issue":"1","key":"CR28","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF01046996","volume":"4","author":"P. Tetali","year":"1991","unstructured":"P. Tetali, Random walks and effective resistance of networks.J. Theoret. Probability 4(1) (1991), 101?109.","journal-title":"J. Theoret. Probability"},{"key":"CR29","unstructured":"W. Thomson and P. G. Tait,Treatise on Natural Philosophy. Cambridge, 1879."},{"issue":"6","key":"CR30","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/0020-0190(91)90091-U","volume":"38","author":"D. I. Zuckerman","year":"1991","unstructured":"D. I. Zuckerman, On the time to traverse all edges of a graph.Inform. Process. Lett. 38(6) (1991), 335?337.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"CR31","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1137\/0405007","volume":"5","author":"D. I. Zuckerman","year":"1992","unstructured":"D. I. Zuckerman, A technique for lower bounding the cover time.SIAM J. Disc. Math. 5(1) (1992), 81?87.","journal-title":"SIAM J. Disc. Math."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270385.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01270385\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01270385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,28]],"date-time":"2024-12-28T09:13:15Z","timestamp":1735377195000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01270385"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,12]]}},"alternative-id":["BF01270385"],"URL":"https:\/\/doi.org\/10.1007\/bf01270385","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,12]]}}}