
Evènement pour le groupe Algorithmique Distribuée
Date  20110502 14:0015:00 
Titre  Spanner, distance oracle, and compact routing for unweighted graphs 
Résumé  It is known that every nvertex 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 datastructure (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.

Lieu  s. 178 
Orateur  Cyril Gavoille 
Aucun document lié à cet événement. RetourRetour à l'index
 