Approximate Distance Oracles with Improved Query Time

Details Approximate Distance Oracles with Improved Query Time Approximate Distance Oracles with Improved Query Time

2012-02-10

arxiv.org/abs/1202.2336v2

Computer Science

Discrete Mathematics

Minor additions

Scientific paper

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\geq 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},\sqrt km + kn^{1 + c/\sqrt k}\})$ time for some constant $c$. This improves the $O(k)$ query time of Thorup and Zwick. For any $0 < \epsilon \leq 1$, we also give an oracle of size $O(kn^{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 Erd\H{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(\log n/\log\log n)$.

Affiliated with

Also associated with

No associations

Rating

Approximate Distance Oracles with Improved Query Time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate Distance Oracles with Improved Query Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Distance Oracles with Improved Query Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-276338