Sémidoc 27 janvier 2011

Quentin Godroy (LaBRI)

 

 

27 janvier 2011
Quelques résultats sur les spanneurs de graphes.

 

 

 

Un spanneur H d'un graphe G est un sous graphe couvrant qui approxime la distance moyennant une économie sur le nombre d'arêtes. Après avoir rappelé la définition et leur motivation, il sera montré quelques algorithmes standards de spanneurs. Par la suite nous montrerons qu'il est possible d'étendre la définition afin de fournir plus de garanties telle que la résistance aux fautes ou la multiconnexité.