Connexité dans l'urgence

Abstract

Nous présentons une structure de données permettant de répondre rapidement aux requêtes de connexité dans un réseau en présence d'un nombre arbitraire de sommets ou de liens défaillant. Plus précisément, après le pré-calcul d'un graphe $G$, on peut déterminer si $u$ et $v$ sont connectés dans le graphe $G\setminus X$ pour toute paire de sommets $u,v$ et tout sous-ensemble $X$ de sommets ou d'arêtes de $G$. Le temps de réponse ne dépend que de $|X|$ et du genre de $G$. La structure de données d'espace $O(gn)$ peut être distribuée en $n$ étiquettes de $O(g\log n)$ bits.