Etant 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.
Tags : Laurent Viennot, Inria, Spanners de graphes, spanner