The DOI matches its Crossref record; 8 of the 8 references it cites were found in a registry or an index.
Reachability and Distance Queries via 2-Hop Labels
Abstract
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs and yet require fast query answering. We propose a new data structure for representing all distances in a graph. The data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v. Our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. For shortest paths, such a cover is a collection S of shortest paths such that, for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from S. We describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. Our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries. We study the proposed data structure using a combination of theoretical and experimental means. We implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. Our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
A Greedy Heuristic for the Set-Covering Problem
Chvatal, V. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.3.233 · Cited by 2,581
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
On the ratio of optimal integral and fractional covers
Lovász, L. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90058-8 · Cited by 1,114
A Fast Parametric Maximum Flow Algorithm and Applications
Gallo, G., Grigoriadis, M. D., & Tarjan, R. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218003 · Cited by 427
Kortsarz, G., & Peleg, D. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1032 · Cited by 136
Proximity-preserving labeling schemes
Peleg, D. (2000) · Journal of Graph Theory · doi:10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5 · Cited by 125
Efficient Parallel Shortest-Paths in Digraphs with a Separator Decomposition
Cohen, E. (1996) · Journal of Algorithms · doi:10.1006/jagm.1996.0048 · Cited by 32
Self-citation
Research works printed but not linked: 2
- Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, IEEE Computer Soc., Los Alamitos, CA, 2001, 242–2511948712 · doi:10.1109/sfcs.2001.959898
- M. Thorup and U. Zwick, Approximate distance oracles , in Proceedings of the 33th Annual ACM Symposium on Theory of Computing, Crete, Greece, 2001, pp. 183–192. · DOI
Cited by
A Survey of Autonomous Driving: Common Practices and Emerging Technologies
Yurtsever, E., Lambert, J., Carballo, A., & Takeda, K. (2020) · IEEE Access · doi:10.1109/access.2020.2983149 · Cited by 1,889
“One possible solution to this is to use hub labeling (HL) [248].”
BackgroundBadue, C., Guidolini, R., Carneiro, R. V., Azevedo, P., Cardoso, V. B., Forechi, A., Jesus, L., Berriel, R., Paixão, T. M., Mutz, F., et al. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113816 · Cited by 1,209
Route Planning in Transportation Networks
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_2 · Cited by 610
Graphs-at-a-time: query language and access methods for graph databases
He, H., & Singh, A. K. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376660 · Cited by 450
Graph pattern matching: from intractable to polynomial time
Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., & Wu, Y. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920878 · Cited by 285
Metadata
- Authors
- Cohen, E., Halperin, E., Kaplan, H., & Zwick, U.
- Venue
- SIAM Journal on Computing
- Published
- 2003-01
- Volume
- 32
- Issue
- 5
- Pages
- 1338-1355
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W1994924587
- Cited by
- 518
- References
- 8
- Citations by year
- 2026: 19 · 2025: 34 · 2024: 32 · 2023: 32 · 2022: 28 · 2021: 34 · 2020: 26 · 2019: 29 · 2018: 24 · 2017: 27 · 2016: 26 · 2015: 38 · 2014: 23 · 2013: 37 · 2012: 18
- FWCI
- 5.15
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Keywords
- reachability queries, distance queries, shortest path, graph data structures, transitive closure, approximate shortest paths, large-scale graphs
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Reachability and Distance Queries via 2-Hop Labels. https://app.cochat.ai/papers/10.1137/s0097539702403098
- The paper
- Cohen, E., Halperin, E., Kaplan, H., & Zwick, U. (2003). Reachability and Distance Queries via 2-Hop Labels. SIAM Journal on Computing. https://doi.org/10.1137/s0097539702403098
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.