Accueil/ expose
From spanners to distance oracles and compact routing
mercredi 01 avril 2015

Loading the player...
Descriptif

Conférence de Laurent Viennot organisée par le département d'informatique.

Exposé donné en français.

A classical area of research is devoted to compact data-structures in networks. Among all, the most prominent algorithmic problem of networks consists in routing. This basically consists in assigning some table at each node of a network and some label identifying each destination so that given his table and the label of the destination of a packet, a node can decide where to forward the packet. Many results of the domain concerns the trade-off between the quantity of information that is stored at each node and the quality of the routes this information provide. We will see that this problem is related to that of finding a spanner of the network that is a subgraph which approximates the original graph of the network with respect to distances: how many links can you remove from a graph without stretching too much distances ? This also leads to the problem of finding a compact distance oracle that is a data structure that approximates the distances inside a graph. The distributed version of the problem consists in assigning a small label to each node so that an estimation of the distance between two nodes can be computed from their two labels (without any auxiliary data-structure). Finally, we will see that this kind of techniques have recently been applied to road networks where distance labels offer an elegant solution for computing driving directions.

Voir aussi


  • Aucun exposé du même auteur.
  • Recent Progress in Leakage-Resilient Cry...
    Yevgeniy Dodis
  • Composer le temps
    Gérard Berry
  • Approximation Bounds for Sparse Principa...
    Alexandre D’Aspremont
  • Diviser-pour-Régner & Inférence Statisti...
    Michael I. Jordan
  • Logarithmes discrets dans les corps fini...
    Antoine Joux
  • Une théorie de l'information mentale
    Claude Berrou
  • Exponential Mechanism for Social Welfar...
    Sampath Kannan
  • Untangling knots using combinatorial opt...
    Benjamin Burton
  • De la convexité tropicale aux jeux répé...
    Stéphane Gaubert
  • A Foundation for Flow-Based Program Matc...
    Julia Lawall
  • Comment faire confiance à un compilateu...
    Xavier Leroy
  • Construction à large couverture de la re...
    Benoît Crabbé
  • Définir et mesurer la complexité : la t...
    Jean-Paul Delahaye
  • Rendre la virgule flottante plus rigoure...
    Jean-Michel Muller
  • Approximations for stochastic graph rewr...
    Vincent Danos
  • Social Networks : a research vision and ...
    Peter Marbach
  • Three discrete geometric structures and ...
    Nabil Mustafa
  • Cognitive Computing
    Jérôme Pesenti
  • Vers les nouvelles bases de données pers...
    Serge Abiteboul
  • Structured Parallel Programming Primitiv...
    Vivek Sarkar
  • Manipuler les réseaux euclidiens
    Damien Sthelé
  • Réduction de modèles de voies de signali...
    Jérôme Feret
  • Le patient numérique personnalisé
    Nicholas Ayache
  • Scade 6: conception d'un langage de prog...
    Bruno Pagano
  • Co-Adaptive Instruments. Can we reinven...
    Wendy Mackay
  • Analyse de pire temps d’exécution et pro...
    Pascal Raymond
  • Chiffrer mieux pour (dé)chiffrer plus
    Anne Canteaut
  • New Results at the Crossroads of Convexi...
    Sébastien Bubeck
Auteur(s)
Laurent Viennot
INRIA
Directeur de recherche

Plus sur cet auteur
Voir la fiche de l'auteur

Cursus :

Laurent Viennot est chercheur en algorithmique des réseaux à l’INRIA.

Cliquer ICI pour fermer
Annexes
Téléchargements :
   - Télécharger la vidéo
   - Télécharger l'audio (mp3)

Dernière mise à jour : 20/04/2015