Approximate Distance Oracle with Constant Query Time

2013/05/14 by Chechik, Shiri · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1305.3314

Abstract

An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes. In this paper we consider approximate distance oracles for general undirected graphs with non-negative edge weights with constant query time. We present a distance oracle of size O(k n^1+1/k), with 2k-1 stretch and O(1) query time. This improves the O(logk) query time of Wulff-Nilsen's distance oracle [SODA '13], which in turn improved the O(k) query time of Thorup and Zwick's distance oracle [J. ACM '05].

Cited by

• Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
• Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
• New approximate distance oracles and their applications
• Improved 2-Approximate Shortest Paths for close vertex pairs

Related

• New approximate distance oracles and their applications
• Approximate Distance Oracles with Improved Query Time
• Approximate Distance Oracles with Improved Preprocessing Time
• Approximate distance oracles
• Constant Query Time (1 + ε)-Approximate Distance Oracle for Planar Graphs