Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths

Let G = (V, E) be a weighted undirected graph with |V| = n and |E| = m. An estimate deltacirc(u,v) of the distance delta(u,v) in G between u,v isin V is said to be of stretch t iff delta(u,v) les deltacirc(u,v) les t middot delta(u,v). The most efficient algorithms known for computing small stretch distances in G are the approximate distance oracles of (M. Thorup and U. Zwick, 2005) and the three algorithms in (E. Cohen and U. Zwick, 2001) to compute all-pairs stretch t distances for t = 2, 7/3, and 3. We present faster algorithms for these problems. For any integer k ges 1, Thorup and Zwick (2005) gave an O(kmn¹k/) algorithm to construct a data structure of size O(kn^{1 + 1}k/) which, given a query (u,v) isin V times V, returns in O(k) time, a 2k - 1 stretch estimate of delta(u, v). But for small values of k, the time to construct the oracle is rather high. Here we present an O(n² log n) algorithm to construct such a data structure of size O(kn¹⁺¹k/) for all integers k ges 2. Our query answering time is O(k) for k > 2 and Theta (log n) for k = 2. We use a new generic scheme for all-pairs approximate shortest paths for these results. This scheme also enables us to design faster algorithms for all-pairs t-stretch distances for t = 2 and 7/3, and compute all-pairs almost stretch 2 distances in O(n² log n) time