Computer Science – Discrete Mathematics
Scientific paper
2012-02-10
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)$.
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-276338