Spanners de graphes

Laurent Viennot, LIAFA - INRIA & Université Paris 7
16 décembre 2010
Abstract
Étant donné un graphe G, un spanner est un sous graphe H qui couvre tous les sommets de G. On s'intéresse alors à deux paramètres : la distance dans H par rapport à la distance dans G, et la taille de H en nombre d'arêtes. L'optimisation simultanée de ces deux paramètres conduit à des compromis que nous mettrons en évidence.
This entry was posted in Events