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

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

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

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

Cluster 2

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