Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00612
Efficient PointtoPoint Resistance Distance Queries in Large Graphs
Vol. 27, no. 1, pp. 3544, 2023. Regular paper.
Abstract We describe a method to efficiently compute pointtopoint 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 edgecuts. 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 edgecut of the graph. Exact queries then require $O(k\log n)$ worstcase time and $O(k)$ averagecase time. Approximate values may be obtained significantly faster by applying standard dimension reduction techniques to the ''coordinates'' stored in the structure.
This work is licensed under the terms of the CCBY license.

Submitted: October 2022.
Reviewed: December 2022.
Revised: January 2023.
Accepted: February 2023.
Final: February 2023.
Published: February 2023.
Communicated by
Giuseppe Liotta

Journal Supporters
