The electrical resistance of a graph captures its commute and cover times
type: Item
instance of: scholarly article
title: The electrical resistance of a graph captures its commute and cover times
zbMATH Open document ID: 0905.60049
DOI: 10.1007/BF01270385
author: Ashok K. Chandra
author: Prabhakar Raghavan
author: Walter L. Ruzzo
author: Roman Smolensky
author: Prasoon Tiwari
published in: Computational Complexity
publication date: 1999-01-19T00:00:00Z
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 68Q99
zbMATH DE Number: 1151784
zbMATH Keywords: random walk
zbMATH Keywords: resistance
zbMATH Keywords: cover time
zbMATH Keywords: commute time
MaRDI profile type: Publication
cites work: On the time taken by random walks on finite groups to visit every state
cites work: Eigenvalues and expanders
cites work: Short Random Walks on Graphs
cites work: Two Applications of Inductive Counting for Complementation Problems
cites work: Lower bounds on the length of universal traversal sequences
cites work: Bounds on the cover time
cites work: Trading Space for Time in Undirected s-t Connectivity
cites work: Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
cites work: Q3706275
cites work: A random polynomial-time algorithm for approximating the volume of convex bodies
cites work: Expanding graphs contain all small trees
cites work: Random walks on graphs
cites work: Approximating the Permanent
cites work: On the cover time of random walks on graphs
cites work: Bounds for eigenvalues of certain stochastic matrices
cites work: Covering problems for Brownian motion on spheres
cites work: Constructing disjoint paths on expander graphs
cites work: Q3993079
cites work: The cover time of a regular expander is O(n log n)
cites work: The fundamental theorem of electrical networks
cites work: Random walks and the effective resistance of networks
cites work: On the time to traverse all edges of a graph
cites work: A Technique for Lower Bounding the Cover Time
description: scientific article; zbMATH DE number 1151784