## Invited Session Mon.3.H 3008

#### Monday, 15:15 - 16:45 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Distances in graphs

**Chair: Christian Wulff-Nilsen and Glencora Borradaile**

**Monday, 15:15 - 15:40 h, Room: H 3008, Talk 1**

**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 + n*^{2}/α) 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 *Õ(n*^{2/3}). Our distance oracles, then, return stretch *2* distances using space *O(n*^{4/3}) and stretch *5/3* distances using space *O(n*^{5/3}).

**Monday, 15:45 - 16:10 h, Room: H 3008, Talk 2**

**Christian Wulff-Nilsen**

Approximate distance oracles with improved preprocessing and query time

**Abstract:**

Given an undirected graph *G* with *m* edges, *n* vertices, and non-negative edge weights, and given an integer *k ≥ 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},√k m + kn^{1 + c/√k }}) time for some constant *c*. This simultaneously improves the *O(kmn*^{1/k}) preprocessing and the *O(k)* query time of Thorup and Zwick. For any *0< ε ≤ 1*, we also give an oracle of size *O(kn*^{1 + 1/k}) that answers *((2 + ε)k)*-approximate distance queries in *O(1/ε)* 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?s. We can match the *O(n*^{1 + 1/k}) size bound of Mendel and Naor for any constant *ε > 0* and *k = O(**log* n/*log**log* n).

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

**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