Approximate distance oracles with improved query time

DOI10.1137/1.9781611973105.39MaRDI QIDQ5741747zbMATH OpenOpenAlexFDO

Authors Christian Wulff-Nilsen

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.2336

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Abstract: Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $kgeq2$, we show that a $(2k-1)$-approximate distance oracle for $G$ of size $O(k{n}^{1+1/k})$ and with $O(logk)$ query time can be constructed in $O(minkm{n}^{1/k},sqrtkm+k{n}^{1+c/sqrtk})$ time for some constant $c$. This improves the $O(k)$ query time of Thorup and Zwick. Furthermore, for any $0<epsilonleq1$, we give an oracle of size $O(k{n}^{1+1/k})$ that answers $((2+epsilon)k)$-approximate distance queries in $O(1/epsilon)$ 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 ErdH{o}s. We can match the $O(n^{1+1/k})$ size bound of Mendel and Naor for any constant $epsilon>0$ and $k=O(logn/loglogn)$.

Recommendations

• Approximate distance oracles with constant query time
• Approximate distance oracles with improved preprocessing time
• Approximate distance oracles
• Approximate distance oracles
• Approximate distance oracles with improved bounds

Cited in

(24)

• Constructing Light Spanners Deterministically in Near-Linear Time
• Approximate shortest paths guided by a small index
• Approximate distance oracles
• An axiomatic approach to time-dependent shortest path oracles
• Approximating approximate distance oracles
• Distance sensitivity oracles with subcubic preprocessing time and fast query time
• Approximate distance oracles with improved bounds
• Approximate distance oracles with improved stretch for sparse graphs
• Approximate distance oracles with improved stretch for sparse graphs
• Approximate distance oracles with constant query time
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Distance oracles beyond the Thorup-Zwick bound
• Approximate distance oracles with improved preprocessing time
• Path-reporting distance oracles with logarithmic stretch and linear size
• Path-reporting distance oracles with linear size
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Approximate distance oracles
• Constructing light spanners deterministically in near-linear time
• On the complexity of the (approximate) nearest colored node problem
• Space-efficient path-reporting approximate distance oracles
• Approximate Shortest Paths Guided by a Small Index

This page was built for publication: Approximate distance oracles with improved query time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741747)