The Taub Faculty of Computer Science Events and Talks

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 e?ciently, 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 T (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, Patrascu and Roditty (2010) broke the long-standing theoretical status-quo in the ?eld 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. In FOCS'12 Patrascu, Roditty and Thorup extended this result to a new in?nity of space stretch trade-o? values. In the talk I will discuss these recent developments.