The electrical resistance of a graph captures its commute and cover times
From MaRDI portal
Publication:1386176
DOI10.1007/BF01270385zbMath0905.60049MaRDI QIDQ1386176
Prabhakar Raghavan, Roman Smolensky, Prasoon Tiwari, Walter L. Ruzzo, Ashok K. Chandra
Publication date: 19 January 1999
Published in: Computational Complexity (Search for Journal in Brave)
Related Items (max. 100)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Kron Reduction and Effective Resistance of Directed Graphs ⋮ The power of two choices for random walks ⋮ Coherence in a family of tree networks with an application of Laplacian spectrum ⋮ Lattice Green/Neumann function for the 2D Laplacian operator defined on square lattice on cylinders, tori and other geometries with some applications ⋮ Forest formulas of discrete Green's functions ⋮ Random walk hitting times and effective resistance in sparsely connected Erdős‐Rényi random graphs ⋮ Modeling spatial networks by contact graphs of disk packings ⋮ Pseudoinverses of Signed Laplacian Matrices ⋮ Bounding robustness in complex networks under topological changes through majorization techniques ⋮ Spectral analysis of weighted neighborhood networks ⋮ Expanded Koch networks: structure and trapping time of random walks ⋮ Kemeny's constant and global mean first passage time of random walks on octagonal cell network ⋮ Relations between scaling exponents in unimodular random graphs ⋮ Anomalous scaling regime for one-dimensional Mott variable-range hopping ⋮ Extremal regime for one-dimensional Mott variable-range hopping ⋮ Geometric bounds on the fastest mixing Markov chain ⋮ Unnamed Item ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Topology-hiding computation on all graphs ⋮ Universal traversal sequences with backtracking. ⋮ Further results on the expected hitting time, the cover cost and the related invariants of graphs ⋮ The local limit of uniform spanning trees ⋮ Graph coarsening: from scientific computing to machine learning ⋮ Randomly biased walks on subcritical trees ⋮ Some further results on the maximal hitting times of trees with some given parameters ⋮ Maximum hitting time for random walks on graphs ⋮ On the cover time and mixing time of random geometric graphs ⋮ Two-point resistances and random walks on stellated regular graphs ⋮ Simple random walk on the uniform infinite planar quadrangulation: Subdiffusivity via pioneer points ⋮ Random Walks with the Minimum Degree Local Rule Have $O(n^2)$ Cover Time ⋮ On the resistance distance and Kirchhoff index of a linear hexagonal (cylinder) chain ⋮ Minimising the expected commute time ⋮ Memory Efficient Anonymous Graph Exploration ⋮ On the mean and variance of cover times for random walks on graphs ⋮ Spectral analysis for a family of treelike networks ⋮ Spectral analysis of three invariants associated to random walks on rounded networks with 2n-pentagons ⋮ A discrete random walk on the hypercube ⋮ A spectrum of time-space trade-offs for undirected \(s-t\) connectivity ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Decomposing hitting times of walks on graphs into simpler ones ⋮ Stable limit laws for randomly biased walks on supercritical trees ⋮ Computing an expected hitting time for the 3-urn Ehrenfest model via electric networks ⋮ Hitting time quasi-metric and its forest representation ⋮ Length lower bounds for reflecting sequences and universal traversal sequences ⋮ An Electric Network for Nonreversible Markov Chains ⋮ Average Resistance of Toroidal Graphs ⋮ Incremental Computation of Pseudo-Inverse of Laplacian ⋮ A Spectral Approach to Network Design ⋮ Collecting coupons on trees, and the cover time of random walks ⋮ Data Analytics on Graphs Part I: Graphs and Spectra on Graphs ⋮ A tight lower bound on the cover time for random walks on graphs ⋮ Random walk on barely supercritical branching random walk ⋮ Approximate span programs ⋮ Deconstructing 1-Local Expanders ⋮ Inferring models of gene expression dynamics ⋮ On the equivalence of cylinder tilings and planar electric networks ⋮ A tight upper bound on the cover time for random walks on graphs ⋮ Symmetric Walks on Paths and Cycles ⋮ On state estimation for nonlinear systems under random access wireless protocols ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ A collection of results concerning electric resistance and simple random walk on distance-regular graphs ⋮ On the inverse mean first passage matrix problem and the inverse \(M\)-matrix problem ⋮ Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs ⋮ Commute times for a directed graph using an asymmetric Laplacian ⋮ Mixing time of near-critical random graphs ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Cover times, blanket times, and majorizing measures ⋮ An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification ⋮ Effective Resistance Preserving Directed Graph Symmetrization ⋮ Harmonic analysis for resistance forms. ⋮ CONVERGENCE RATE AND GLOBAL MEAN WEIGHTED FIRST-PASSAGE TIME IN A 1D CHAIN NETWORK WITH A WEIGHTED ADDING REVERSE EDGE ⋮ A recursion formula for resistance distances and its applications ⋮ Asymptotics of cover times via Gaussian free fields: bounded-degree graphs and general trees ⋮ Graph Clustering using Effective Resistance ⋮ Concentration of the Kirchhoff index for Erdős-Rényi graphs ⋮ Extrema of the Two-Dimensional Discrete Gaussian Free Field ⋮ Random walks on graphs and Monte Carlo methods ⋮ The Evolution of the Cover Time ⋮ The Cover Time of Cartesian Product Graphs ⋮ Potential induced random teleportation on finite graphs ⋮ Critical random graphs: Diameter and mixing time ⋮ Optimizing network robustness by edge rewiring: a general framework ⋮ Effective resistances for supercritical percolation clusters in boxes ⋮ Expected cover times of random walks on symmetric graphs ⋮ Cover times for sequences of reversible Markov chains on random graphs ⋮ Tight bounds for the cover time of multiple random walks ⋮ EXPANSION CONSTANTS AND HYPERBOLIC EMBEDDINGS OF FINITE GRAPHS ⋮ The effective resistance of the \(N\)-cycle graph with four nearest neighbors ⋮ Convergence of metric graphs and energy forms ⋮ Random walks and flights over connected graphs and complex networks ⋮ Unnamed Item ⋮ Developments in the theory of randomized shortest paths with a comparison of graph node distances ⋮ Unnamed Item ⋮ Expected hitting times for random walks on quadrilateral graphs and their applications ⋮ Cover time in edge-uniform stochastically-evolving graphs ⋮ Return probability and recurrence for the random walk driven by two-dimensional Gaussian free field ⋮ On hitting times of random walks on trees ⋮ Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters ⋮ On planar graphs of uniform polynomial growth
Cites Work
- Unnamed Item
- Unnamed Item
- Random walks and the effective resistance of networks
- The cover time of a regular expander is O(n log n)
- Expanding graphs contain all small trees
- Covering problems for Brownian motion on spheres
- Eigenvalues and expanders
- Bounds for eigenvalues of certain stochastic matrices
- On the time to traverse all edges of a graph
- Lower bounds on the length of universal traversal sequences
- Random walks on graphs
- Constructing disjoint paths on expander graphs
- Bounds on the cover time
- On the cover time of random walks on graphs
- Coalescing random walks and voter model consensus times on the torus in \({\mathbb{Z}}^ d\)
- Approximating the Permanent
- Two Applications of Inductive Counting for Complementation Problems
- On the time taken by random walks on finite groups to visit every state
- A Technique for Lower Bounding the Cover Time
- Trading Space for Time in Undirected s-t Connectivity
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Short Random Walks on Graphs
- The fundamental theorem of electrical networks
This page was built for publication: The electrical resistance of a graph captures its commute and cover times
