Approximate Distance Oracles with Improved Preprocessing Time

Details Approximate Distance Oracles with Improved Preprocessing Time Approximate Distance Oracles with Improved Preprocessing Time

2011-09-19

arxiv.org/abs/1109.4156v1

Computer Science

Discrete Mathematics

To appear at the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, 2012

Scientific paper

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\geq 1$, we show that for some universal constant $c$, a $(2k-1)$-approximate distance oracle for $G$ of size $O(kn^{1 + 1/k})$ can be constructed in $O(\sqrt km + kn^{1 + c/\sqrt k})$ time and can answer queries in $O(k)$ time. We also give an oracle which is faster for smaller $k$. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all $k\geq 6$ and improve the $O(kmn^{1/k})$ time bound of Thorup and Zwick except for very sparse graphs and small $k$. When $m = \Omega(n^{1 + c/\sqrt k})$ and $k = O(1)$, our oracle is optimal w.r.t.\ both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erd\H{o}s.

Affiliated with

Also associated with

No associations

Rating

Approximate Distance Oracles with Improved Preprocessing 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 Preprocessing Time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Distance Oracles with Improved Preprocessing Time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-145659