Laurent Viennot
16 décembre 2010
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.