Connexité dans l'urgence

Nous presentons une structure de donnees permettant de repondre rapidement aux requetes de connexite dans un reseau en presence d'un nombre arbitraire de sommets ou de liens defaillant. Plus precisement, apres le pre-calcul d'un graphe $G$, on peut determiner si $u$ et $v$ sont connectes dans le graphe $G\setminus X$ pour toute paire de sommets $u,v$ et tout sous-ensemble $X$ de sommets ou d'aretes de $G$. Le temps de reponse ne depend que de $|X|$ et du genre de $G$. La structure de donnees d'espace $O(gn)$ peut etre distribuee en $n$ etiquettes de $O(g\log n)$ bits.