%0 Conference Paper %1 chandra89 %A Chandra, Ashok K. %A Raghavan, Prabhakar %A Ruzzo, Walter L. %A Smolensky, Roman %B Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing %C New York, NY, USA %D 1989 %E Johnson, David S. %I ACM %K circuit effective.resistance graph.theory network resistor %P 574--586 %R 10.1145/73007.73062 %T The Electrical Resistance of a Graph Captures its Commute and Cover Times %X View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems. %@ 0-89791-307-8

@inproceedings{chandra89, abstract = {View an n-vertex, m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with the lengths of random walks on the graph. For example, the commute time between two vertices s and t (the expected length of a random walk from s to t and back) is precisely characterized by the effective resistance Rst between s and t: commute time = 2mRst. Additionally, the cover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistance R in the graph to within a factor of log n: mR ≤ cover time ≤ O (mR log n). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, using this approach, we improve known bounds on cover times for various classes of graphs, including high-degree graphs, expanders, and multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.}, acmid = {73062}, added-at = {2016-05-04T11:10:41.000+0200}, address = {New York, NY, USA}, author = {Chandra, Ashok K. and Raghavan, Prabhakar and Ruzzo, Walter L. and Smolensky, Roman}, biburl = {https://www.bibsonomy.org/bibtex/285535bbe5c0155be221be51f08089c5a/ytyoun}, booktitle = {Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing}, doi = {10.1145/73007.73062}, editor = {Johnson, David S.}, interhash = {b2875167e64a28faac2e3baf06f30e24}, intrahash = {85535bbe5c0155be221be51f08089c5a}, isbn = {0-89791-307-8}, keywords = {circuit effective.resistance graph.theory network resistor}, location = {Seattle, Washington, USA}, numpages = {13}, pages = {574--586}, publisher = {ACM}, series = {STOC '89}, timestamp = {2016-09-15T09:40:27.000+0200}, title = {The Electrical Resistance of a Graph Captures its Commute and Cover Times}, year = 1989 }