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


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



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

Christian Wulff-Nilsen
Approximate distance oracles with improved preprocessing and query time


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(kn1 + 1/k) and with O(log k) query time can be constructed in O(min{kmn1/k,√k m + kn1 + c/√k }) time for some constant c. This simultaneously improves the O(kmn1/k) preprocessing and the O(k) query time of Thorup and Zwick. For any 0< ε ≤ 1, we also give an oracle of size O(kn1 + 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(n1 + 1/k) size bound of Mendel and Naor for any constant ε > 0 and k = O(log n/loglog n).



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

Liam Roditty
A survey on distance oracles

Coauthors: Mihai Patrascu, Mikkel Thorup


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 Θ(mn1/k) time and generate a compact data structure of size O(n1+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(n5/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


  The deal is that Indiana Payday Loans online can save your time, nerves and make a solution of all your financial problems. It is strictly forbidden to administrate Cialis Soft online in conjunction with medications, which are composed of nitrates - antidepressants, drastic analgetic pills, sleeping pills, and others.