Evènement pour le groupe Algorithmique Distribuée

Date 2011-05-02  14:00-15:00
TitreSpanner, distance oracle, and compact routing for unweighted graphs 
RésuméIt is known that every n-vertex unweighted graph G has a subgraph H of O(n^1.5) edges such that the distance in H between any two vertices is at most the distance in G plus 2. In other words, there is always a graph of size O(n^1.5) that well approximate all distances in G. It is however not known whether every graph has a data-structure (a distance oracle) of space O(n^1.5) supporting (d+2)-approximate distance query in constant time. In this direction, Patrascu and Roditty have recently showed in FOCS'11 that distance oracle of size O(n^1.66) and (2d+1)-approximate distance query in constant time do exists. In this talk, I will show a distributed version of this oracle matching its space and distance approximation bounds, and a generalization of it. I will also present a compact routing scheme using tables of size O(n^0.75) and whose route lengths are at most twice the distance plus one.  
Lieus. 178 
OrateurCyril Gavoille 

Aucun document lié à cet événement.

Retour à l'index