Evènement pour le groupe Algorithmique Distribuée
|Date|| 2011-05-02 14:00-15:00|
|Titre||Spanner, 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.
|Lieu||s. 178 |
|Orateur||Cyril Gavoille |
Aucun document lié à cet événement.RetourRetour à l'index