Close to linear space routing schemes

DOI10.1007/S00446-015-0256-5zbMath1352.68197OpenAlexW2231128115MaRDI QIDQ5964899

Liam Roditty, Roei Tov

Publication date: 1 March 2016

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-015-0256-5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Approximate distance oracles with improved stretch for sparse graphs ⋮ Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Compact Routing in Unit Disk Graphs ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Routing in Polygonal Domains

Cites Work

• Unnamed Item
• Unnamed Item
• Preprocess, set, query!
• Compact Routing with Minimum Stretch
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Improved routing strategies with succinct tables
• Approximate distance oracles
• Spanners and emulators with sublinear distance errors
• Routing with Polynomial Communication-Space Trade-Off
• Distributed Computing: A Locality-Sensitive Approach
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• A trade-off between space and efficiency for routing tables
• Compact routing schemes with low stretch factor
• All-Pairs Almost Shortest Paths
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Distance Oracles for Sparse Graphs
• Compact routing schemes with improved stretch
• Approximate distance oracles with constant query time
• Distance Oracles beyond the Thorup--Zwick Bound
• Distance Oracles for Stretch Less Than 2

This page was built for publication: Close to linear space routing schemes