Reachability and Distance Queries via 2-Hop Labels

DOI10.1137/S0097539702403098zbMath1026.68165OpenAlexW1994924587MaRDI QIDQ4429688

Uri Zwick, Haim Kaplan, Edith Cohen, Eran Halperin

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539702403098

zbMATH Keywords

reachability queriesshortest-path queries2-hop labelsdistance labels

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Discrete mathematics in relation to computer science (68R99)

Related Items (19)

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended ⋮ Access, Rank, and Select in Grammar-compressed Strings ⋮ Lower Bounds in the Preprocessing and Query Phases of Routing Algorithms ⋮ Eccentricity queries and beyond using hub labels ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ On the Complexity of Hub Labeling (Extended Abstract) ⋮ Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs ⋮ Reachability in big graphs: a distributed indexing and querying approach ⋮ Customizable hub labeling: properties and algorithms ⋮ Unnamed Item ⋮ VC-Dimension and Shortest Path Algorithms ⋮ Randomized proof-labeling schemes ⋮ Shortest-path queries in static networks ⋮ Approximate shortest paths guided by a small index ⋮ Unnamed Item ⋮ Efficient single-pair all-shortest-path query processing for massive dynamic networks ⋮ Reachability oracles for directed transmission graphs ⋮ The hierarchical hub labeling is non-efficient ⋮ Computing Constrained Shortest-Paths at Scale

This page was built for publication: Reachability and Distance Queries via 2-Hop Labels