Monday, 15:15 - 15:40 h, Room: H 3008

 

Rachit Agarwal
The space-stretch-time tradeoff in distance oracles

 

Abstract:
We present distance oracles for weighted undirected graphs that return distances of stretch 2 and less. For the realistic case of sparse graphs, our distance oracle exhibit the three-way trade-off between space, stretch and query time - a phenomenon that does not occur in dense graphs. In particular, for any positive integer t and for any 1 ≤ α ≤ n, our distance oracle is of size O(m + n2/α) and returns stretch (1+2/(t+1)) distances in time O((α Δ)t), where Δ = 2m/n is the average degree of the graph. The query time can be further reduced to O((α + Δ)t) at the expense of a small additive stretch.
Consider, for example, the realistic case of graphs with m = Õ(n) edges and fix the query time to be Õ(n2/3). Our distance oracles, then, return stretch 2 distances using space O(n4/3) and stretch 5/3 distances using space O(n5/3).

 

Talk 1 of the invited session Mon.3.H 3008
"Distances in graphs" [...]
Cluster 2
"Combinatorial optimization" [...]

 

  online loans . If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.