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.
Catégories: Séminaire général du département d'informatique
Mot-clés : internet, information, algorithme, réseau, ordinateur, routage
Voir aussi
|
|
Cursus :
Laurent Viennot est chercheur en algorithmique des réseaux à l’INRIA.
Cliquer ICI pour fermerDernière mise à jour : 20/04/2015
Tous droits réservés
@ 2011 ENS