Preprocess, set, query!

DOI10.1007/s00453-013-9825-9zbMath1307.68094OpenAlexW2178691795MaRDI QIDQ2017874

Ely Porat, Liam Roditty

Publication date: 23 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9825-9

zbMATH Keywords

data structuresgraph algorithmsdistance oracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (4)

A Hierarchy of Lower Bounds for Sublinear Additive Spanners ⋮ Shortest-path queries in static networks ⋮ Close to linear space routing schemes ⋮ Approximate distance oracles with improved stretch for sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Ramsey partitions and proximity data structures
• Approximate distance oracles
• Spanners and emulators with sublinear distance errors
• Compact Routing in Power-Law Graphs
• Graph spanners
• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• Distance Oracles for Sparse Graphs
• Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
• Distance Oracles beyond the Thorup--Zwick Bound
• Distance Oracles for Stretch Less Than 2
• Computing almost shortest paths

This page was built for publication: Preprocess, set, query!