Reachability and Distance Queries via 2-Hop Labels
From MaRDI portal
Publication:4429688
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
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