Distance Oracles beyond the Thorup--Zwick Bound
From MaRDI portal
Publication:5419041
DOI10.1137/11084128XzbMath1310.68117OpenAlexW2158860088MaRDI QIDQ5419041
Publication date: 4 June 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/11084128x
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items
Approximate distance oracles with improved stretch for sparse graphs ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Distance oracles for time-dependent networks ⋮ Longest common extensions in trees ⋮ A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Longest Common Extensions in Trees ⋮ Compressed dynamic range majority and minority data structures ⋮ General space-time tradeoffs via relational queries ⋮ Unnamed Item ⋮ Dynamic and internal longest common substring ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Range closest-pair search in higher dimensions ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Distance Oracles for Vertex-Labeled Graphs ⋮ Shortest-Path Queries in Geometric Networks ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Preprocess, set, query! ⋮ Unnamed Item ⋮ Close to linear space routing schemes ⋮ On Approximate Distance Labels and Routing Schemes with Affine Stretch ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Unnamed Item ⋮ Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Navigating planar topologies in near-optimal space and time ⋮ Unnamed Item ⋮ Unnamed Item
