Efficient Point-to-Point Resistance Distance Queries in Large Graphs

Craig Gotsman, Kai Hormann

Research output: Contribution to journalArticlepeer-review


We describe a method to efficiently compute point-to-point resistance distances in a graph, which are notoriously difficult to compute from the raw graph data. Our method is based on a relatively compact hierarchical data structure which “compresses” the resistance distance data present in a graph, constructed by a nested bisection of the graph using compact edge-cuts. Built and stored in a preprocessing step (which is amenable to massive parallel processing), efficient traversal of a small portion of this data structure supports efficient and exact answers to resistance distance queries. The size of the resulting data structure for a graph of n vertices is O(nk log n), where k is the size of a balanced edge-cut of the graph. Exact queries then require O(k log n) worst-case time and O(k) average-case time. Approximate values may be obtained significantly faster by applying standard dimension reduction techniques to the “coordinates” stored in the structure.

Original languageEnglish (US)
Pages (from-to)35-44
Number of pages10
JournalJournal of Graph Algorithms and Applications
Issue number1
StatePublished - 2023

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Computer Science Applications
  • Geometry and Topology
  • Computational Theory and Mathematics


Dive into the research topics of 'Efficient Point-to-Point Resistance Distance Queries in Large Graphs'. Together they form a unique fingerprint.

Cite this