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.