Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

Guoren Wang; Meihao Liao; Rong-Hua Li; Yueyang Pan

REVIEW 4 major objections 4 minor 79 references

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Exact resistance distance becomes a tree-path sum.

desk verdict TreeIndex is the first exact tree-decomposition labelling for resistance distance and shows dramatic speedups on road networks, but the correctness proof has two real gaps (Lemma 3.9's support claim and a false Lemma 4.4) that are fixable rather than fatal. read the letter →

arxiv 2509.05129 v1 pith:YG2NHKHL submitted 2025-09-05 cs.DB cs.DMcs.DScs.LG

Meihao Liao , Yueyang Pan , Rong-Hua Li , Guoren Wang This is my paper · ORCID

classification cs.DBcs.DMcs.DScs.LG

keywords resistancedistancetreedecompositiongraphlabellingLaplacianeffectivesmalltreewidthroadnetworksexactqueries

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that resistance distance—a graph metric that accounts for all paths, not just the shortest—can be computed exactly by storing a small label per vertex derived from a tree decomposition. The central identity expresses r(s,t) as a sum of squared label ratios along the paths from s and t to the root of the decomposition. If true, this reduces single-pair query time to O(tree height) and enables exact single-source queries in O(n·tree height), making resistance distance practical on road networks with millions of nodes. The paper backs this with a construction algorithm that builds the labels in O(n·h²·d_max) time using rank-1 updates, and reports experiments where queries on the full USA road network take about 10⁻³ seconds.

What carries the argument

The resistance distance labelling S[v,u], defined as the u-th element of the v-th column of the inverse Laplacian submatrix L⁻¹_UU at the moment vertex v is eliminated in the MDE tree decomposition. The key identity is Lemma 3.10: the three-term sum above. The mechanism is Gaussian elimination on the inverse Laplacian, which decomposes it into rank-1 outer products indexed by elimination order; the tree decomposition's vertex hierarchy guarantees the labelling's support matches root paths, so only O(tree height) labels per query are needed.

What would settle it

Take a small graph (4-8 nodes), compute the full pseudo-inverse of its Laplacian directly with exact arithmetic, build the MDE tree decomposition and the TreeIndex labels, then check every pair (v,u) to see whether S[v,u]=0 matches the ancestor relation in the tree. A single mismatch on a pair along a root path breaks the claim.

Watch

Extended reading notes

Core claim

The core claim is that in a minimum-degree-elimination (MDE) tree decomposition, the resistance distance r(s,t) equals a sum over labels along the paths from s and t to the root: r(s,t) = Σ_{v∈P_s\LCA} (S[v,s])²/S[v,v] + Σ_{v∈P_t\LCA} (S[v,t])²/S[v,v] + Σ_{v∈P_{LCA→root}} (S[v,s]-S[v,t])²/S[v,v]. This follows from expanding the pseudo-inverse of the Laplacian as a sum of rank-1 outer products (inverse Cholesky), and observing, via the cut property of resistance distance, that the labelling S[v,u] is non-zero precisely when v is an ancestor of u in the decomposition tree. Consequently, only labels along the two root paths and the LCA-to-root path are needed, which is what makes compact labell

Load-bearing premise

The labelling entries are non-zero exactly when one vertex is an ancestor of the other in the decomposition tree; if that fails—extra non-zeros or missing path entries—the query sums no longer equal the true resistance distance.

Editorial extensions

If this is right

If true, exact single-pair resistance distance queries on small-treewidth graphs (road networks) become O(tree height), comparable to shortest-path labelling methods.
Single-source exact queries become O(n·tree height), enabling applications like electrical-flow-based robust routing on country-scale road networks.
Index construction time O(n·h²·d_max) is practical for graphs where h and d_max are small constants, with a reported 7-hour build for a 24-million-node graph.
The labelling size O(n·h) is large but loadable in memory on commodity servers (405 GB for Full-USA).
Existing random-walk approximate methods become unnecessary for such graphs; exact answers are reported faster than approximations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The dependency property likely extends beyond MDE decompositions to any elimination ordering that yields a tree decomposition with the vertex hierarchy property; if so, the method could be paired with balanced decompositions to reduce label size on non-road graphs.
The support conjecture (Lemma 3.9) is the fragile point: if the MDE process can disconnect a subtree before elimination, the formula silently drops terms and returns the wrong resistance; a small counterexample or proof patch would settle it.
The same rank-1/labelling logic might transfer to other matrix functions of the Laplacian (hitting times, currents), possibly yielding similar tree-path formulas.
The reported exactness relies on floating-point arithmetic in practice; the paper's own precision analysis bounds errors below 10⁻¹¹ on tested graphs, but adversarial or ill-conditioned graphs could amplify this.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing to know: TreeIndex is the first tree-decomposition labelling for exact resistance distance, and on the Full-USA road network it answers exact single-pair queries in under a millisecond and single-source queries in ~190 seconds—orders of magnitude faster than the exact and approximate baselines they compare against. That result is worth taking seriously even though the correctness proof has two real gaps.

What the paper does well: the linear algebra core is standard Schur complement / rank-1 update material (Lemmas 3.4-3.7, 4.3), and the dependency property (Lemma 3.10) is a genuinely new closed form: r(s,t) as a sum of squared label differences along the s-to-root and t-to-root paths. The construction algorithm is a clever bottom-up rank-1 update that matches the tree structure, and the complexity bounds (label size O(n*h), query O(h)) are credible. The experiments are extensive and the precision check against LapSolver on NewYork and Road-PA (absolute error <1e-11) is good evidence the method is computing the right numbers on real inputs.

The soft spots, in order of importance. First, Lemma 3.9—the zero/nonzero support structure of the labelling—is doing all the work in Lemma 3.10 and in the query algorithms, but its proof is a few sentences asserting connectivity rather than a demonstration. If the true support is any larger or smaller than the paths-to-root, every query result changes. The paper never shows that the induced subgraph on the subtree of v is connected in the original graph (as opposed to the filled graph). I believe the claim is likely true, but it is not proven, and it is the linchpin.

Second, Lemma 4.4 is simply false as stated: a processed neighbor of v_i can be a grandchild, not only a child—a 3-cycle is a counterexample. The algorithm's while loop probably still works under the weaker 'ancestor' property, but the lemma needs to be corrected and the complexity proof re-examined.

Third, the pseudocode has a garbled variable (v_w on line 8 should be w), and the experimental 'ground truth' on large graphs is TreeIndex itself, which is self-referential; the small-graph validation mitigates this but should be stated more transparently.

Bottom line: the gaps are in the proof, not in the core idea. The paper is for the graph-data-management audience and anyone who needs exact resistance distance on road-scale networks. It deserves a serious referee and, after the structural lemmas are tightened, likely acceptance. Send it out.

Referee Report

4 major / 4 minor

Summary. The paper proposes TreeIndex, an exact indexing method for resistance-distance queries on graphs with small treewidth. The central idea is to combine the cut property of resistance distance (expressed via Schur complements and a rank-1 decomposition of the inverse Laplacian) with a minimum-degree-elimination (MDE) tree decomposition. The authors claim that the resistance distance r(s,t) depends only on labels stored along the paths from s and t to the root of the tree decomposition (Lemma 3.10), that a labelling of size O(n·h_G) can be built in O(n·h_G^2·d_max) time, and that single-pair and single-source queries take O(h_G) and O(n·h_G) time, respectively. Experiments on road and social networks, including the full USA road network, are reported, and the method is compared with random-walk, Laplacian-solver, and index-based baselines.

Significance. If the correctness arguments are completed, this would be a notable contribution: it is, to my knowledge, the first resistance-distance labelling scheme with sublinear query time for small-treewidth graphs, and the experiments suggest practical scalability to graphs with tens of millions of nodes. The paper also makes a useful conceptual connection between the Cholesky/Schur-complement structure of the inverse Laplacian and the elimination-tree hierarchy of an MDE tree decomposition. The claimed complexity bounds, O(n·h_G) space and O(h_G) query time, are attractive and, if realized, bring resistance-distance queries close to the performance of shortest-path hierarchical labelling. The authors provide source code and extensive experiments, which strengthens the practical claims. However, the central correctness proof currently rests on an insufficiently justified support-structure lemma, and the construction pseudocode contains a concrete normalization error; these issues must be resolved before the exactness claim can be accepted.

major comments (4)

[§3.2, Lemma 3.9] Lemma 3.9 is the load-bearing support claim: it asserts that S[v,u] is nonzero exactly when u is in the subtree of v in the MDE tree decomposition. The proof does not establish this. The sentence 'due to the connectivity between v and nodes in its subtree' asserts the needed connectivity of the processed subgraph induced by {v} ∪ SubTree(v), but no proof is given that this induced subgraph is connected, nor that every processed node outside SubTree(v) is disconnected from v in that subgraph. Both the dependency property (Lemma 3.10) and Algorithms 2 and 3 rely on setting all non-path terms to zero; any violation of this pattern changes the computed resistance distance by an omitted squared term. A rigorous proof must be supplied, using the MDE elimination-tree structure (e.g., showing that original edges only join ancestor-descendant pairs and that descendants of v form the connected com
[§4.2, Algorithm 1, lines 12–14] The normalization step is written incorrectly. Line 12 sets S[v_i,v_i] = 1/δ, where δ = d_{v_i} − Σ_{w∈N(v_i)∩U} S[v_i,w]. Line 14 then divides every u in SubTree(v_i) by the same δ. Since SubTree(v_i) includes v_i under the paper's own convention (see Example 9 and Lemma 4.1), the diagonal entry is divided by δ twice. For the first processed node in a triangle, d=2 and U∩N(v)=∅, so δ=2; line 12 gives S[v_i,v_i]=1/2, then line 14 changes it to 1/4, whereas the 1×1 principal submatrix [d] has inverse 1/2. The update loop must be over SubTree(v_i)\{v_i}, or the off-diagonal entries must be normalized differently (e.g., multiplied by S[v_i,v_i]). This is a concrete correctness bug in the construction algorithm.
[§4.2, Lemma 4.4] Lemma 4.4 states that for every w ∈ N(v_i)∩U, v_i is the parent of w in T_min. This is false. In a 3-cycle with MDE elimination order 1,2,3, the elimination tree is the path 1→2→3. When processing v_i=3, U contains {1,2} and N(3)∩U contains 1; but 1 is a grandchild of 3, not a child. The while-loop in Algorithm 1 still terminates because v_i is an ancestor of w, but the lemma as stated is incorrect. The proof of Lemma 4.6 cites Lemma 4.4 to bound the work; if the ancestor relation is weaker than parent, the nested-subtree argument needs to be restated (the stated O(n·d_max·h_G^2) bound may still hold, but the current proof does not show it). This lemma should be corrected or replaced with a precise ancestor-statement and the complexity proof adjusted accordingly.
[§3.2, Lemma 3.10 / Algorithm 2 path range] Lemma 3.10 sums over 'P_{LCA→root}', which is ambiguous: Algorithm 2 stops at the root (line 12: while w ≠ T_min.root), and the root's label S[root,·] is not constructed by Algorithm 1 because the root is never added to U. Example 10 also excludes the root. The statement should explicitly define the path ranges used in Lemma 3.10, and the proof should make clear why the root term is absent. As written, a reader could conclude that the sum includes a nonexistent label.

minor comments (4)

[§4.1, Lemma 4.1] The indexing formula appears to have u and v swapped. The text says 'S[v,u] can be visited via S[u].res[DFSOrder[u]−DFSOrder[v]]', but Example 11 correctly uses S[v].res[DFSOrder[u]−DFSOrder[v]]. Please correct the lemma statement.
[§4.2, Lemma 4.2] The proof says S[u].res stores values for all nodes in the path from u to the root, but the labelling structure (Lemma 4.1 and Figure 5) stores values for the subtree rooted at u. This discrepancy should be fixed.
[§6.1] The experiments set ground truth using TreeIndex itself. Exp III provides an independent check against LapSolver on two datasets, but the manuscript should qualify that the ground-truth statement in §6.1 is only a self-consistency reference and that independent verification was performed separately.
[Throughout] There are several typos and notation inconsistencies (e.g., 'qery' in Problem 1, 'eletrical flow' in Lemma 5.1, 'Defiend' in Definition 2, and the unresolved subscripts in the statement of Lemma 3.10). A careful proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the labelling formula follows from algebraic rank-1 decomposition; the fragile Lemma 3.9 support claim is a proof gap, not an input-output equivalence.

full rationale

The paper's derivation chain is not circular. Resistance distance is first expressed via the pseudo-inverse (Eq. 1), a standard identity. The cut property (Lemma 3.7) is obtained by combining the Schur-complement formula of Theorem 2.1 (cited from the authors' LEIndex paper) with the Cholesky/Gaussian-elimination decomposition of Lemmas 3.4-3.6. Theorem 2.1 is a parameter-free, externally checkable matrix identity; citing it as a starting point is legitimate and does not smuggle in the paper's own target result. Lemmas 3.4-3.6 are proved in-text via block-matrix inversion and rank-1 updates, so the crucial identity L^{-1}_{U2U2} - diag(L^{-1}_{U1U1},0) = sum_k S[:,v_k]S[:,v_k]^T/S[v_k,v_k] is derived, not assumed. Lemma 3.10 then partitions this exact sum by the sparsity pattern of the labelling; if Lemma 3.9's support claim held, the formula would be forced by algebra rather than by construction. The query algorithms (Algorithms 2 and 3) only evaluate that formula, and no parameter is fitted to the target queries. The experimental sections use TreeIndex itself as 'ground truth' for comparing approximate methods, but Exp III independently cross-checks against LapSolver at epsilon=1e-19; this is a self-referential evaluation choice, not a circular derivation. The genuine concern is that Lemma 3.9's proof is incomplete: it asserts 'connectivity between v and nodes in its subtree' without establishing that the relevant inverse-M-matrix entries are nonzero exactly on the subtree, and Lemma 4.4's claim that every processed neighbor is a child is false in general. Those are correctness gaps in the exactness proof, not circularity. The self-citations to [48] and [49] provide standard formulas that do not include the claimed dependency property, so they do not make the derivation circular.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's central derivation rests on two structural assumptions about the MDE tree decomposition that are not fully proven here: the non-zero support pattern of the labels and the parent relation for processing edges. The non-zero support is the critical one: if it fails, the dependency property formula omits terms and queries return wrong answers. The paper supplies only a one-sentence justification. The rest of the argument is standard linear algebra (Schur complements, rank-1 updates).

assumptions (5)

domain assumption The MDE heuristic tree decomposition satisfies the vertex hierarchy property: for any bag X_u, all nodes in X_u except u are ancestors of u; the LCA and its ancestors form a vertex cut.
Lemma 3.8 is quoted from [13] and is the bridge between tree decomposition structure and the cut property. The proof is not reproduced in this paper.
ad hoc to paper The non-zero support of the resistance distance labelling S[v,u] is exactly the set of (v,u) where u is in the subtree of v (equivalently v on path from u to root).
Lemma 3.9 asserts this structural property with a sketch ('due to the connectivity between v and nodes in its subtree'), but the proof does not rigorously establish connectivity within the remaining vertex set. The entire dependency property (Lemma 3.10) and both query algorithms rely on this support pattern.
ad hoc to paper For any edge (v_i, w) with w processed before v_i in the reverse DFS order, v_i is the parent of w in the tree decomposition.
Lemma 4.4 makes this claim to guarantee termination of the while loop; the proof in the paper asserts it without a detailed argument, and the statement may be false for general minimum-degree orderings where adjacent nodes can be at distance >1 in the elimination tree.
standard math The relation e_s^T L_v^{-1} e_t = tau_v[s,t] / d_t
Used in Lemma 3.1 proof; this is a standard random-walk interpretation of the reduced Laplacian inverse, cited to [48].
standard math Standard linear algebra: block-matrix inverse formula, Schur complement, and rank-1 update properties.
Used throughout Section 3 and in Lemma 4.3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach." pith.science (2026). https://pith.science/paper/YG2NHKHL

@misc{pith2026250905129,
  author       = {Pith},
  title        = {Pith review of: Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YG2NHKHL}},
  note         = {Machine review of arXiv:2509.05129}
}

abstract

Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance $r(s,t)$ depends only on labels along the paths from $s$ and $t$ to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose \treeindex, a novel index method that constructs a resistance distance labelling of size $O(n \cdot h_{\mathcal{G}})$ in $O(n \cdot h_{\mathcal{G}}^2 \cdot d_{\max})$ time, where $h_{\mathcal{G}}$ (tree height) and $d_{\max}$ (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in $O(h_{\mathcal{G}})$ time and single-source queries in $O(n \cdot h_{\mathcal{G}})$ time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a $405$ GB labelling in $7$ hours (single-threaded) and answers exact single-pair queries in $10^{-3}$ seconds and single-source queries in $190$ seconds--the first exact method scalable to such large graphs.

Figures

Figures reproduced from arXiv: 2509.05129 by the authors.

**Figure 3.** An illustrative example of the cut property of resis [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 4.** An illustrative example of tree decomposition and [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

Figures from the paper (8 more)

**Figure 5.** Figure 5: An example of the labelling structure on T𝑚𝑖𝑛. The resulting labelling framework comprises two main components: (i) the tree decomposition T𝑚𝑖𝑛, and (ii) the resistance distance labelling S. For the first part, the tree decomposition T𝑚𝑖𝑛 is stored as a tree structure.…

**Figure 6.** Figure 6: An illustrative example of robust routing on road [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]

**Figure 9.** Figure 9: Processing time of single-source query Email-enron DBLPAmazon New YorkRoad-PARoad-TXRoad-CAWestern Road-CTR Full-USA 10 1 10 0 10 1 10 2 10 3 Average Absolute Error LEwalk LEIndex [PITH_FULL_IMAGE:figures/full_fig_p014_9.png]

**Figure 10.** Figure 10: Average absolute error of single-source query for [PITH_FULL_IMAGE:figures/full_fig_p014_10.png]

**Figure 11.** Figure 11: Precision analysis of TreeIndex and LapSolver [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]

**Figure 12.** Figure 12: Scalability test on road networks and synthetic [PITH_FULL_IMAGE:figures/full_fig_p015_12.png]

**Figure 13.** Figure 13: Performance of TreeIndex when varying treewidth Plateau Method Path 1 Path 2 Path 3 Path 4 Path 5 Start End Harvard Bridge Boston University MIT Campus Harvard University Penalty Method Path 1 Path 2 Path 3 Path 4 Path 5 Start End Harvard Bridge Boston University MIT …

**Figure 14.** Figure 14: Comparison of different routing methods from [PITH_FULL_IMAGE:figures/full_fig_p016_14.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

79 extracted references · 75 canonical work pages

[1]

CAMVIT: Choice routing

2009. CAMVIT: Choice routing. http://www.camvit.com. Accessed: 2024-06-23

work page 2009
[2]

Goldberg, and Renato Fonseca F

Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck

work page
[3]

Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. InSIGMOD. 349–360

work page 2013
[4]

Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph Clustering using Effective Resistance. InITCS (LIPIcs, Vol. 94). 41:1–41:16

work page 2018
[5]

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat

work page
[6]

Haris Angelidakis, Yury Makarychev, and Vsevolod Oparin. 2017. Algorithmic and Hardness Results for the Hub Labeling Problem. InSODA. 1442–1461

work page 2017
[7]

Anonymous Authors. 2025. Efficient Exact Resistance Distance Compu- tation on Small-Treewidth Graphs: a Labelling Approach.Full version: https://anonymous.4open.science/r/TreeIndex-32E9(2025)

work page 2025
[8]

Roland Bader, Jonathan Dees, Robert Geisberger, and Peter Sanders. 2011. Al- ternative Route Graphs in Road Networks. InICST Conference, TAPAS (Lecture Notes in Computer Science, Vol. 6595). 21–32

work page 2011

Show all 79 references

[9]

Bodlaender

Hans L. Bodlaender. 2006. Treewidth: Characterizations, Applications, and Com- putations. InGraph-Theoretic Concepts in Computer Science, 32nd International Workshop. 1–14

2006
[10]

1998.Modern graph theory

Béla Bollobás. 1998.Modern graph theory. Vol. 184

1998
[11]

Boman, Kevin Deweese, and John R

Erik G. Boman, Kevin Deweese, and John R. Gilbert. 2016. An Empirical Com- parison of Graph Laplacian Solvers. InALENEX. 174–188

2016
[12]

Dongrun Cai, Xue Chen, and Pan Peng. 2023. Effective Resistances in Non- Expander Graphs. InESA, Vol. 274. 29:1–29:18

2023
[13]

Lijun Chang, Jeffrey Xu Yu, Lu Qin, Hong Cheng, and Miao Qiao. 2012. The exact distance to destination in undirected world.VLDB J.21, 6 (2012), 869–888

2012
[14]

Chao Chen, Tianyu Liang, and George Biros. 2021. RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems.SIAM J. Sci. Comput.43, 6 (2021), C411–C438

2021
[15]

Zitong Chen, Ada Wai-Chee Fu, Minhao Jiang, Eric Lo, and Pengfei Zhang
[16]

Fan Chung and Linyuan Lu. 2002. Connected components in random graphs with given expected degree sequences.Annals of combinatorics6, 2 (2002), 125–145

2002
[17]

1997.Spectral graph theory

Fan RK Chung. 1997.Spectral graph theory. Vol. 92. American Mathematical Soc

1997
[18]

Edith Cohen. 1994. Polylog-time and near-linear work approximation scheme for undirected shortest paths. InSTOC. 16–26

1994
[19]

Edith Cohen, Eran Halperin, Haim Kaplan, and Uri Zwick. 2002. Reachability and distance queries via 2-hop labels. InSODA. 937–946

2002
[20]

Cohen, Rasmus Kyng, Gary L

Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearlymlog 1/2ntime. InSTOC. 343–352

2014
[21]

Vincent Cohen-Addad, Søren Dahlgaard, and Christian Wulff-Nilsen. 2017. Fast and Compact Exact Distance Oracle for Planar Graphs. InFOCS. 962–973

2017
[22]

Dennis de Champeaux and Lenie Sint. 1977. An Optimality Theorem for a Bi-Directional Heuristic Search Algorithm.Comput. J.20, 2 (1977), 148–150

1977
[23]

Camil Demetrescu, Andrew Goldberg, and David Johnson. 2009. The shortest path problem: Ninth DIMACS implementation challenge. https://www.diag. uniroma1.it/challenge9

2009
[24]

Karel Devriendt, Samuel Martin-Gutierrez, and Renaud Lambiotte. 2022. Variance and Covariance of Distributions on Graphs.SIAM Rev.64, 2 (2022), 343–359

2022
[25]

Karel Devriendt, Andrea Ottolini, and Stefan Steinerberger. 2024. Graph curvature via resistance distance.Discret. Appl. Math.348 (2024), 68–78

2024
[26]

Rajat Vadiraj Dwaraknath, Ishani Karmarkar, and Aaron Sidford. 2023. Towards Optimal Effective Resistance Estimation. InNIPS

2023
[27]

Michael Elkin and Ofer Neiman. 2016. Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. InFOCS. 128–137

2016
[28]

Muhammad Farhan, Henning Koehler, Robert Ohms, and Qing Wang. 2023. Hierarchical Cut Labelling - Scaling Up Distance Queries on Road Networks. Proc. ACM Manag. Data1, 4 (2023), 244:1–244:25

2023
[29]

Muhammad Farhan, Henning Koehler, and Qing Wang. 2025. Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks.Proc. ACM Manag. Data3, 1 (2025), 35:1–35:25

2025
[30]

Arash Farzan and Shahin Kamali. 2011. Compact Navigation and Distance Oracles for Graphs with Small Treewidth. InICALP. 268–280. SIGMOD ’26, June 03–05, 2026, Woodstock, NY Meihao Liao, Yueyang Pan, Rong-Hua Li, and Guoren Wang

2011
[31]

Ada Wai-Chee Fu, Huanhuan Wu, James Cheng, and Raymond Chi-Wing Wong
[32]

Spielman

Yuan Gao, Rasmus Kyng, and Daniel A. Spielman. 2023. Robust and Practical So- lution of Laplacian Equations by Approximate Elimination.CoRRabs/2303.00709 (2023)

2023 arXiv
[33]

Cyril Gavoille, David Peleg, Stephane Perennes, and Ran Raz. 2001. Distance labeling in graphs. InSODA. 210–219

2001
[34]

Goldberg and Chris Harrelson

Andrew V. Goldberg and Chris Harrelson. 2005. Computing the shortest path:A search meets graph theory. InSODA. 156–165

2005
[35]

2013.Matrix computations

Gene H Golub and Charles F Van Loan. 2013.Matrix computations. JHU press

2013
[36]

Siddharth Gupta, Adrian Kosowski, and Laurent Viennot. 2019. Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. InICALP, Vol. 132. 143:1–143:15

2019
[37]

Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. 2016. Efficient Algorithms for Spanning Tree Centrality. InIJCAI. 3733–3739

2016
[38]

Williamson

Monika Henzinger, Billy Jin, Richard Peng, and David P. Williamson. 2023. A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. Algorithmica85, 12 (2023), 3680–3716

2023
[39]

Arun Jambulapati and Aaron Sidford. 2021. Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers. InSODA. 540–559

2021
[40]

Minhao Jiang, Ada Wai-Chee Fu, Raymond Chi-Wing Wong, and Yanyan Xu
[41]

Henning Koehler, Muhammad Farhan, and Qing Wang. 2025. Stable Tree La- belling for Accelerating Distance Queries on Dynamic Road Networks. InEDBT. 477–489

2025
[42]

Adrian Kosowski and Laurent Viennot. 2017. Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. InSODA. 1462–1478

2017
[43]

Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. InFOCS. 573–582

2016
[44]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data

2014
[45]

Lawrence Li and Sushant Sachdeva. 2023. A New Approach to Estimating Effec- tive Resistances and Counting Spanning Trees in Expander Graphs. InSODA. 2728–2745

2023
[46]

Wentao Li, Miao Qiao, Lu Qin, Ying Zhang, Lijun Chang, and Xuemin Lin. 2020. Scaling Up Distance Labeling on Graphs with Core-Periphery Properties. In SIGMOD. 1367–1381

2020
[47]

Meihao Liao, Cheng Li, Rong-Hua Li, and Guoren Wang. 2025. Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs.Proc. ACM Manag. Data3, 1 (2025), 36:1–36:27

2025
[48]

Meihao Liao, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, Hongchao Qin, and Guoren Wang. 2023. Efficient Resistance Distance Computation: The Power of Landmark-based Approaches.Proc. ACM Manag. Data1, 1 (2023), 68:1–68:27

2023
[49]

Meihao Liao, Junjie Zhou, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, and Guoren Wang. 2024. Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach.Proc. ACM Manag. Data2, 3 (2024), 133

2024
[50]

Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang. 2023. CurvDrop: A Ricci Curvature Based Approach to Prevent Graph Neural Networks from Over-Smoothing and Over-Squashing. InWWW. 221–230

2023
[51]

Takanori Maehara, Takuya Akiba, Yoichi Iwata, and Ken-ichi Kawarabayashi
[52]

Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. 2010. Measuring the mixing time of social graphs. InSIGCOMM. 383–389

2010
[53]

OpenStreetMap contributors. 2017. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org

2017
[54]

Dian Ouyang, Lu Qin, Lijun Chang, Xuemin Lin, Ying Zhang, and Qing Zhu. 2018. When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks. InSIGMOD. 709–724

2018
[55]

Dian Ouyang, Long Yuan, Lu Qin, Lijun Chang, Ying Zhang, and Xuemin Lin
[56]

Benjamin Pachev and Benjamin Webb. 2018. Fast link prediction for large net- works using spectral embedding.Journal of Complex Networks6, 1 (2018), 79–94

2018
[57]

VLDB7, 12 (2014), 1023–1034

Computing Personalized PageRank Quickly by Exploiting Graph Structures. VLDB7, 12 (2014), 1023–1034

2014
[58]

Yi Qi, Wanyue Xu, Liwang Zhu, and Zhongzhi Zhang. 2021. Real-World Networks Are Not Always Fast Mixing.Comput. J.64, 2 (2021), 236–244

2021
[59]

Neil Robertson and Paul D. Seymour. 1984. Graph minors. III. Planar tree-width. J. Comb. Theory B36, 1 (1984), 49–64

1984
[60]

Sushant Sachdeva and Yibin Zhao. 2023. A Simple and Efficient Parallel Laplacian Solver. InSPAA. 315–325

2023
[61]

Jieming Shi, Nikos Mamoulis, Dingming Wu, and David W. Cheung. 2014. Density- based place clustering in geo-social networks. InSIGMOD. 99–110

2014
[62]

Ali Kemal Sinop, Lisa Fawcett, Sreenivas Gollapudi, and Kostas Kollias. 2021. Robust Routing Using Electrical Flows. InSIGSPATIAL. 282–292

2021
[63]

Spielman and Nikhil Srivastava

Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. InSTOC. 563–568

2008
[64]

Pan Peng, Daniel Lopatta, Yuichi Yoshida, and Gramoz Goranci. 2021. Local Algorithms for Estimating Effective Resistance. InKDD. 1329–1338

2021
[65]

Bronstein

Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. 2022. Understanding over-squashing and bottlenecks on graphs via curvature. InICLR

2022
[66]

Fang Wei. 2010. TEDI: efficient shortest path query answering on graphs. In SIGMOD. 99–110

2010
[67]

Renchi Yang and Jing Tang. 2023. Efficient Estimation of Pairwise Effective Resistance.Proc. ACM Manag. Data1, 1 (2023), 16:1–16:27

2023
[68]

Hongzhi Yin, Bin Cui, Jing Li, Junjie Yao, and Chen Chen. 2012. Challenging the Long Tail Recommendation.VLDB5, 9 (2012), 896–907

2012
[69]

Mengxuan Zhang, Lei Li, Wen Hua, Rui Mao, Pingfu Chao, and Xiaofang Zhou
[70]

Yikai Zhang and Jeffrey Xu Yu. 2022. Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks. InSIGMOD. 1992–2005

2022
[71]

Prasad Tetali. 1991. Random walks and the effective resistance of networks. Journal of Theoretical Probability4, 1 (1991), 101–109

1991
[77]

Dynamic Hub Labeling for Road Networks. InICDE. 336–347
[79]

Bolong Zheng, Yong Ma, Jingyi Wan, Yongyong Gao, Kai Huang, Xiaofang Zhou, and Christian S. Jensen. 2023. Reinforcement Learning based Tree Decomposition for Distance Querying in Road Networks. InICDE. 1678–1690

2023
[2010]

Highway Dimension, Shortest Paths, and Provably Efficient Algorithms. In SODA. 782–793
[2013]

IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying.VLDB6, 6 (2013), 457–468

2013
[2014]

Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks.VLDB7, 12 (2014), 1203–1214

2014
[2016]

InESA (LIPIcs, Vol

Sublinear Distance Labeling. InESA (LIPIcs, Vol. 57). 5:1–5:15
[2020]

VLDB Endow.13, 5 (2020), 602–615

Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees.Proc. VLDB Endow.13, 5 (2020), 602–615

2020
[2021]

InSIGMOD

P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators. InSIGMOD. 313–325

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

CAMVIT: Choice routing

2009. CAMVIT: Choice routing. http://www.camvit.com. Accessed: 2024-06-23

work page 2009

[2] [2]

Goldberg, and Renato Fonseca F

Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato Fonseca F. Werneck

work page

[3] [3]

Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. InSIGMOD. 349–360

work page 2013

[4] [4]

Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph Clustering using Effective Resistance. InITCS (LIPIcs, Vol. 94). 41:1–41:16

work page 2018

[5] [5]

Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Ely Porat

work page

[6] [6]

Haris Angelidakis, Yury Makarychev, and Vsevolod Oparin. 2017. Algorithmic and Hardness Results for the Hub Labeling Problem. InSODA. 1442–1461

work page 2017

[7] [7]

Anonymous Authors. 2025. Efficient Exact Resistance Distance Compu- tation on Small-Treewidth Graphs: a Labelling Approach.Full version: https://anonymous.4open.science/r/TreeIndex-32E9(2025)

work page 2025

[8] [8]

Roland Bader, Jonathan Dees, Robert Geisberger, and Peter Sanders. 2011. Al- ternative Route Graphs in Road Networks. InICST Conference, TAPAS (Lecture Notes in Computer Science, Vol. 6595). 21–32

work page 2011