Robustesse des distances et du diamètre dans un réseau fragile

International audienceUne propriété d'un graphe est robuste si elle est satisfaite dans tous ses sous-graphes couvrants connexes.Cette notion de robustesse est un type d'hérédité de propriété motivée par les réseaux dynamiques dont l'emprunte ultime est connexe.Dans cette présentation, nous nous concentrerons sur la robustesse du diamètre dans un graphe classique, à savoir si le diamètre reste le même après la perte d'arêtes. Le diamètre est important pour borner la complexité d'algorithmes distribués.Nous montrerons que décider si le diamètre d'un graphe est robuste est co-NP-complet. À l'inverse, décider si la distance entre deux sommets donnés est robuste peut se faire en temps linéaire en adaptant un algorithme de reconnaissance des graphes série-parallèle