## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 35-44 |

Number of pages | 10 |

Journal | Journal of Graph Algorithms and Applications |

Volume | 27 |

Issue number | 1 |

DOIs | |

State | Published - 2023 |

## All Science Journal Classification (ASJC) codes

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