Approximate Distance Oracles with Improved Query Time

2012/02/10 by Christian Wulff‐Nilsen, Wulff-Nilsen, Christian · 2 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1202.2336

openalex publication_date 2012/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k≥ 2, we show that a (2k-1)-approximate distance oracle for G of size O(kn^{1 + 1/k}) and with O(log k) query time can be constructed in O(min\kmn^1/k,√ km + kn^{1 + c/√ k}\) time for some constant c. This improves the O(k) query time of Thorup and Zwick. Furthermore, for any 0 < ε≤ 1, we give an oracle of size O(kn^{1 + 1/k}) that answers ((2 + ε)k)-approximate distance queries in O(1/ε) time. At the cost of a k-factor in size, this improves the 128k approximation achieved by the constant query time oracle of Mendel and Naor and approaches the best possible tradeoff between size and stretch, implied by a widely believed girth conjecture of Erdős. We can match the O(n^{1 + 1/k}) size bound of Mendel and Naor for any constant ε> 0 and k = O(log n/loglog n).

Cited by

• Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
• Improved 2-Approximate Shortest Paths for close vertex pairs

Related

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