Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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

Cohen, Edith, Halperin, Eran, Kaplan, Haim, Zwick, Uri · 2003 · SIAM Journal on Computing

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

Crossref · 10.1137/s0097539702403098

Cites

8 of 8 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Show all 8 references

Research works printed but not linked: 2

  1. 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
  2. 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

See all 521

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.