Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
Summary: Shows resistance distance on small-treewidth graphs depends only on labels along s/t root paths in a tree decomposition, bypassing costly matrix ops. TreeIndex: O(n h) labelling (build O(n h^2 dmax)), exact single-pair O(h) and single-source O(n h) queries; first exact method scalable to continental road networks. (summarized by gpt-5-mini on Feb 11 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Meihao Liao (Beijing Institute of Technology)
- 2. Yueyang Pan (Beijing Institute of Technology)
- 3. Rong-Hua Li (Beijing Institute of Technology)
- 4. Guoren Wang (Beijing Institute of Technology)
BibTeX Citation
@inproceedings{liao_sigmod26,
title = {{Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach}},
author = {Liao, Meihao and Pan, Yueyang and Li, Rong-Hua and Wang, Guoren},
series = {{SIGMOD} '26},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3769788},
url = {https://dl.acm.org/doi/10.1145/3769788},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,414 | Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs | 2027 | SIGMOD | 4.9605343e-05 |
| 10,813 | Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs | 2026 | VLDB | 4.9605343e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 18 of 18 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next