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

**Liam Roditty**

A survey on distance oracles

**Coauthors: Mihai Patrascu, Mikkel Thorup**

**Abstract:**

Computing distances is one of the most fundamental computational problems. In many applications we are not really interested in *all*

distances, we want the ability to retrieve them quickly. Thorup and Zwick (2005) initiated the theoretical study of data structures capable of representing approximated distances efficiently, in terms of space requirement and query time.

Given an *n*-vertex weighted undirected graph with *m* edges, they show that for any integer *k ≥ 1* it is possible to preprocess the graph in *Θ(mn*^{1/k}) time and generate a compact data structure of size *O(n*^{1+1/k}). For each pair of vertices, it is then possible to retrieve a stretch~*k* approximate distance in *O(k)* time. Recently, P\v{a}tra?cu and Roditty~(2010) broke the long-standing theoretical status-quo in the field of distance oracles. They obtained, in particular, a distance oracle for unweighted graphs of size *O(n*^{5/3}) that can supply in *O(1)* time an estimated distance in the range *[d,2d+1]*, where~*d* is the actual distance between the two vertices queried

Talk 3 of the invited session Mon.3.H 3008

**"Distances in graphs"** [...]

Cluster 2

**"Combinatorial optimization"** [...]