The Electrical Resistance of a Graph Captures Its Commute and Cover Times

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 resistane Rst between s and...

By: Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo (Univ. of WA), Roman Smolensky and Prasoon Tiwari

Published in: Computational Complexity, volume 6, (no 4), pages 312-40 in 1997

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .