The electrical resistance of a graph captures its commute and cover times

No abstract is available for this paper.

• Publication year

  1989

• Venue

  Symposium on the Theory of Computing

• Publication date

  1989-02-01

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1007/BF01270385
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the time to traverse all edges of a graph

  1991cited by this paper
• On the Time to Traverse all Edges of a Graph

  1991cited by this paper
• Random walks and the effective resistance of networks

  1991cited by this paper
• The Cover Time of a Regular Expander is O(n log n)

  1990influential reference
• A technique for lower bounding the cover time

  1990cited by this paper
• Two Applications of Inductive Counting for Complementation Problems

  1989cited by this paper
• Coalescing Random Walks and Voter Model Consensus Times on the Torus in $\mathbb{Z}^d$

  1989cited by this paper
• Approximating the Permanent

  1989cited by this paper
• On the cover time of random walks on graphs

  1989cited by this paper
• Lower bounds on the length of universal traversal sequences

  1989cited by this paper
• Trading space for time in undirected s-t connectivity

  1989cited by this paper
• A random polynomial time algorithm for approximating the volume of convex bodies

  1989cited by this paper
• Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved

  1988cited by this paper
• Covering Problems for Brownian Motion on Spheres

  1988cited by this paper
• Bounds on the cover time

  1988cited by this paper
• Constructing disjoint paths on expander graphs

  1987cited by this paper
• Expanding graphs contain all small trees

  1987cited by this paper
• Eigenvalues and expanders

  1986influential reference
• Random Walks and Electrical Networks

  1984cited by this paper
• On the time taken by random walks on finite groups to visit every state

  1983cited by this paper
• Bounds for eigenvalues of certain stochastic matrices

  1981cited by this paper
• Random walks, universal traversal sequences, and the complexity of maze problems

  1979cited by this paper
• Random walks on graphs

  1974cited by this paper
• The fundamental theorem of electrical networks

  1951cited by this paper
• A Treatise on Electricity and Magnetism: Frontmatter

  year unknowncited by this paper
• Treatise on Natural Philosophy

  year unknowncited by this paper

• Quantitative Study of Urban Ventilation Corridors’ Impact on the Atmospheric Environment Based on Circuit Theory

  2026cites this paper
• Thermodynamic geometry of friction on graphs: Resistance, commute times, and optimal transport

  2026cites this paper
• CBERR: Community-based effective resistance graph rewiring

  2026cites this paper
• Effective Graph Resistance as Cumulative Heat Dissipation

  2026cites this paper
• Impact of converting graphs into spanning trees on node and graph classification in Graph Neural Network

  2026cites this paper
• Random walks and consensus problem on tree network with an identical degree distribution

  2026cites this paper
• SynthWorlds: Controlled Parallel Worlds for Disentangling Reasoning and Knowledge in Language Models

  2025cites this paper
• Learnable Diffusion Distances for Link Prediction

  2025cites this paper
• Resistance distances and Kirchhoff indices in graph joins

  2025cites this paper
• Laplacian Network Optimization via Information Functions

  2025cites this paper
• Scaling limit for the random walk on critical lattice trees

  2025cites this paper
• On the Hitting Time Index of Graphs

  2025cites this paper
• Short-Range Oversquashing

  2025cites this paper
• What is a proper graph Laplacian? An operator-theoretic framework for graph diffusion

  2025cites this paper
• The Resistance Distance Is a Diffusion Distance on a Graph

  2025cites this paper
• GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring

  2025cites this paper
• Benchmark of the Full and Reduced Effective Resistance Kernel for Molecular Classification

  2025cites this paper
• Transmit power policies for stochastic stabilisation of multi-link wireless networked control systems

  2025cites this paper
• Oversmoothing, "Oversquashing", Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning

  2025cites this paper
• Structure-Aware Spectral Sparsification via Uniform Edge Sampling

  2025cites this paper
• Maximally Expressive GNNs for Outerplanar Graphs

  2025cites this paper
• Formulating effective resistance in temporal networks: Models and empirical insights

  2025cites this paper
• dyGRASS: Dynamic Spectral Graph Sparsification via Localized Random Walks on GPUs

  2025influential citation
• SALMAN: Stability Analysis of Language Models Through the Maps Between Graph-based Manifolds

  2025cites this paper
• Computation of resistance distance metric with Kirchhoff index in a class of bi-triangular claw-free graphical network

  2025cites this paper
• Promoting Fairness in Information Access within Social Networks

  2025cites this paper
• Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks

  2025cites this paper
• Efficient community detection in disaster networks using spectral sparsification

  2025cites this paper
• On the jump of the cover time in random geometric graphs

  2025influential citation
• The role of structural connectivity on brain function through a Markov model of signal transmission

  2025cites this paper
• Effective resistance in planar graphs and continued fractions

  2025cites this paper
• Characterization of Complete Bipartite Graphs via Resistance Spectra

  2025cites this paper
• Cequel: Cost-Effective Querying of Large Language Models for Text Clustering

  2025cites this paper
• Modeling, analysis and validation of friendship paradox in evolving networks

  2025cites this paper
• Effects of Dropout on Performance in Long-range Graph Learning Tasks

  2025cites this paper
• Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization

  2025cites this paper
• Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering

  2024cites this paper
• Structural Properties on Scale-Free Tree Network with an Ultra-Large Diameter

  2024cites this paper
• Kemeny’s constant and the Lemoine point of a simplex

  2024cites this paper
• Sensitivity to network perturbations in the randomized shortest paths framework: theory and applications in ecological connectivity

  2024cites this paper
• Kirchhoff index of Vicsek polygon networks and its applications

  2024cites this paper
• Next Level Message-Passing with Hierarchical Support Graphs

  2024cites this paper
• A method for constructing graphs with the same resistance spectrum

  2024cites this paper
• Spectral Graph Pruning Against Over-Squashing and Over-Smoothing

  2024cites this paper
• Revisiting Random Walks for Learning on Graphs

  2024cites this paper
• Dynamic minimisation of the commute time for a one-dimensional diffusion

  2024influential citation
• Study of Random Walk Invariants for Spiro-Ring Network Based on Laplacian Matrices

  2024cites this paper
• Temporal Graph Rewiring with Expander Graphs

  2024cites this paper
• SIGACT News Complexity Theory Column 123

  2024cites this paper
• Computation of resistance distance and Kirchhoff index of chain of triangular bipyramid hexahedron

  2024cites this paper
• Laplacian operator and its square lattice discretization: Green function vs. Lattice Green function for the flat 2-torus and other related 2D manifolds

  2024cites this paper
• Contributions of network structure, chemoarchitecture and diagnostic categories to transitions between cognitive topographies

  2024cites this paper
• Advances in quantum algorithms for the shortest path problem

  2024cites this paper
• Bringing circuit theory into spatial occupancy models to assess landscape connectivity

  2024cites this paper
• Incorporating circuit theory into a dynamic model for crowd-sourced observations of migratory birds

  2024cites this paper
• Node classification in the heterophilic regime via diffusion-jump GNNs

  2024cites this paper
• Sublinear-Time Sampling of Spanning Trees in the Congested Clique

  2024cites this paper
• Property analysis and coherence dynamics for tree-symmetric networks with noise disturbance

  2024cites this paper
• Resistance diameters and critical probabilities of Cayley graphs on irreducible complex reflection groups

  2024cites this paper
• A heuristic method to solve an assignment problem using a random walk approximation

  2024cites this paper
• Entry-Specific Matrix Estimation under Arbitrary Sampling Patterns through the Lens of Network Flows

  2024cites this paper
• Quantum Algorithm for Path-Edge Sampling

  2023cites this paper
• Computing Effective Resistances on Large Graphs Based on Approximate Inverse of Cholesky Factor

  2023cites this paper
• Fast exploration and learning of latent graphs with aliased observations

  2023cites this paper
• Identifying influential nodes based on resistance distance

  2023cites this paper
• Understanding Oversquashing in GNNs through the Lens of Effective Resistance

  2023influential citation
• Transitions between cognitive topographies: contributions of network structure, neuromodulation, and disease

  2023cites this paper
• Dynamic Averaging Load Balancing on Arbitrary Graphs

  2023influential citation
• Community Detection in Dense Networks using Effective Resistance and Link Pruning

  2023cites this paper
• Formulas for Hitting Times and Cover Times for Random Walks on Groups

  2023cites this paper
• Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes

  2023cites this paper
• Kemeny's constant and global mean first passage time of random walks on octagonal cell network

  2023cites this paper
• Resistance Distances in Directed Graphs: Definitions, Properties, and Applications

  2023cites this paper
• Matrix Analysis of Hexagonal Model and Its Applications in Global Mean-First-Passage Time of Random Walks

  2023influential citation
• Locality-Aware Graph-Rewiring in GNNs

  2023cites this paper
• Sampling Balanced Forests of Grids in Polynomial Time

  2023cites this paper
• Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition

  2023cites this paper
• Bounds on Kemeny's constant of a graph and the Nordhaus-Gaddum problem

  2023cites this paper
• Optimal Bounds on Private Graph Approximation

  2023cites this paper
• On the average hitting times of weighted Cayley graphs

  2023cites this paper
• Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover Time

  2023influential citation
• How does over-squashing affect the power of GNNs?

  2023cites this paper
• Diffusion-Jump GNNs: Homophiliation via Learnable Metric Filters

  2023cites this paper
• Random Walks, Conductance, and Resistance for the Connection Graph Laplacian

  2023cites this paper
• Graph Fourier MMD for Signals on Graphs

  2023cites this paper
• University Campus as a Complex Pedestrian Dynamic Network: A Case Study of Walkability Patterns at Texas Tech University †

  2023cites this paper
• Study of mean-first-passage time and Kemeny’s constant of a random walk by normalized Laplacian matrices of a penta-chain network

  2023cites this paper
• Efficient Estimation of Pairwise Effective Resistance

  2023cites this paper
• Lattice Green/Neumann function for the 2D Laplacian operator defined on square lattice on cylinders, tori and other geometries with some applications

  2023cites this paper
• Structural Group Unfairness: Measurement and Mitigation by Means of the Effective Resistance

  2023influential citation
• Multidimensional Quantum Walks

  2023cites this paper
• On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology

  2023influential citation
• Graph-Based Model-Agnostic Data Subsampling for Recommendation Systems

  2023cites this paper
• Infinite Lewis Weights in Spectral Graph Theory

  2023cites this paper
• Over-Squashing in Graph Neural Networks: A Comprehensive survey

  2023cites this paper
• Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality

  2023cites this paper
• Some further results on the maximal hitting times of trees with some given parameters

  2022cites this paper
• Multi-View Random-Walk Graph Regularization Low-Rank Representation for Cancer Clustering and Differentially Expressed Gene Selection

  2022cites this paper
• Genomics and ecological modelling clarify species integrity in a confusing group of butterflies

  2022cites this paper
• Accelerating advances in landscape connectivity modelling with the ConScape library

  2022cites this paper