Speaker: Uri Zwick Tel Aviv University
Time: 2005-09-20 15:30-2005-09-20 16:30
Venue: FIT-1-222, Tsinghua University

Abstract:

Let k>=2 be an integer. We show that any undirected and unweighted graph G=(V,E) on n vertices has a subgraph G'=(V,E') with O(kn^{1+1/k}) edges such that for any two vertices u,v\in V, if d_G(u,v)=d, then d_{G'}(u,v) = d + O(d^{1-\frac{1}{k-1}}). Furthermore, we show that such subgraphs can be constructed in O(mn^{1/k}) time, where m and n are the number of edges and vertices in the original graph. We also show that it is possible to construct a *weighted* graph G^*=(V,E^*) with O(kn^{1+1/(2^{k}-1)}) edges such that for every u,v\in V, if d_G(u,v)=d, then d\le d_{G^*}(u,v) = d + O(d^{1-\frac{1}{k-1}})$. These are the first such results with additive error terms of the form o(d), i.e., additive error terms that are sublinear in the distance being approximated.
Joint work with Mikkel Thorup
 

Short Bio: