Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Random walks and the effective resistance of networks

Prasad Tetali1

(1) Department of Computer Science, Courant Institute of Mathematical Sciences, 10012 New York, New York

Received: 19 June 1989  Revised: 22 January 1990  

Abstract  In this article we present an interpretation ofeffective resistance in electrical networks in terms of random walks on underlying graphs. Using this characterization we provide simple and elegant proofs for some known results in random walks and electrical networks. We also interpret the Reciprocity theorem of electrical networks in terms of traversals in random walks. The byproducts are (a) precise version of thetriangle inequality for effective resistances, and (b) an exact formula for the expectedone-way transit time between vertices.

Key Words  Electrical networks - electrical impedance - random walks - Markov chains


Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this article
Export this article as RIS | Text
 
Referenced by
24 newer articles

  1. Zhang, Zhongzhi (2010) Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees. Physical Review E 81(1)
    [CrossRef]
  2. Zhang, Zhongzhi (2009) Mean first-passage time for random walks on the T-graph. New Journal of Physics 11(10)
    [CrossRef]
  3. Palacios, José Luis (2009) Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks. International Journal of Quantum Chemistry
    [CrossRef]
  4. KASUE, Atsushi (2006) Variational Convergence of Finite Networks. Interdisciplinary Information Sciences 12(1)
    [CrossRef]
  5. Feige, Uriel (1995) A tight lower bound on the cover time for random walks on graphs. Random Structures and Algorithms 6(4)
    [CrossRef]
  6. Tetali, Prasad (1999) Design of On-Line Algorithms Using Hitting Times. SIAM Journal on Computing 28(4)
    [CrossRef]
  7. Grady, Leo (2006) Isoperimetric Partitioning: A New Algorithm for Graph Partitioning. SIAM Journal on Scientific Computing 27(6)
    [CrossRef]
  8. Coppersmith, Don (1993) Collisions Among Random Walks on a Graph. SIAM Journal on Discrete Mathematics 6(3)
    [CrossRef]
  9. Coppersmith, Don (1996) Random Walks on Regular and Irregular Graphs. SIAM Journal on Discrete Mathematics 9(2)
    [CrossRef]
  10. Grady, L. (2006) Random Walks for Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(11)
    [CrossRef]
First | Next | Last
Remote Address: 38.107.191.99 • Server: mpweb24
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)