DBScholar

Back to papers

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)

Paper ID
h1bd477dc4732f7a7
Venue
SIGMOD
Year
2026
Pagerank
4.9793485e-05
Overall Rank
10,564 | 28.98%
DOI
10.1145/3769788

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

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 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
10,742 Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs 2026 VLDB 4.9793485e-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.

Rank Cited Paper Year Venue Pagerank
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025584127
382 TEDI: Efficient Shortest Path Query Answering on Graphs 2010 SIGMOD 0.00019485934
1,368 Computing Personalized PageRank Quickly by Exploiting Graph Structures 2014 VLDB 0.0001090624
1,585 Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks 2014 VLDB 0.00010163696
1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD 9.9953879e-05
1,647 IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying 2013 VLDB 9.9875545e-05
2,141 Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees 2020 VLDB 8.9668034e-05
2,943 P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators 2021 SIGMOD 7.8314485e-05
3,687 Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks 2022 SIGMOD 7.0955331e-05
4,356 Challenging the Long Tail Recommendation 2012 VLDB 6.6409244e-05
4,488 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD 6.5781787e-05
4,743 Density-based Place Clustering in Geo-Social Networks 2014 SIGMOD 6.4396758e-05
5,273 Efficient Estimation of Pairwise Effective Resistance 2023 SIGMOD 6.2007708e-05
6,408 Hierarchical Cut Labelling – Scaling Up Distance Queries on Road Networks 2023 SIGMOD 5.7942038e-05
8,020 Efficient Resistance Distance Computation: the Power of Landmark-based Approaches 2023 SIGMOD 5.4061498e-05
8,629 Efficient and Provable Effective Resistance Computation on Large Graphs: an Index-based Approach 2024 SIGMOD 5.2994494e-05
9,799 Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks 2025 SIGMOD 5.1257999e-05
9,947 Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs 2025 SIGMOD 5.1038322e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD
2 1,252 A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs 2012 SIGMOD
3 774 Efficiently Answering Reachability Queries on Very Large Directed Graphs 2008 SIGMOD
4 1,722 Querying Shortest Paths on Time Dependent Road Networks 2019 VLDB
5 3,934 Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach 2012 SIGMOD
6 4,488 Scaling Up Distance Labeling on Graphs with Core-Periphery Properties 2020 SIGMOD
7 1,645 When Hierarchy Meets 2-Hop-Labeling: Efficient Shortest Distance Queries on Road Networks 2018 SIGMOD
8 8,020 Efficient Resistance Distance Computation: the Power of Landmark-based Approaches 2023 SIGMOD
9 5,336 Efficient Shortest Path Counting on Large Road Networks 2022 VLDB
10 7,377 Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach 2022 VLDB