Stratégies d'encerclement connexes dans un réseau

Description

Le problème de l'encerclement dans les réseaux a été introduit par Parson (1976) : étant donné un réseau ``contaminé'' (par exemple dans lequel un intrus s'est introduit), l'emph{encerclement} du réseau est le nombre minimum d'agents nécessaires pour ``nettoyer'' le réseau (c'est-à-dire capturer l'intrus). Une stratégie d'encerclement est dite connexe si à chaque étape de la stratégie, l'ensemble des liens nettoyés induit un sous-réseau connexe. Les stratégies d'encerclement connexes sont essentielles si l'on souhaite assurer des communications sûres entre les agents. Dans le cas des réseaux en arbres, Barrière {sl et al.} (2002, 2003) ont prouvé que le rapport entre l'encerclement connexe et l'encerclement est majoré par 2, et que cette borne est optimale. Dans cet article, nous donnons une borne pour ce rapport dans le cas des réseaux arbitraires. Pour cela nous utilisons une notion cruciale de théorie des graphes : la largeur arborescente. L'égalité entre la largeur arborescente connexe d'un graphe et sa largeur arborescente découle du théorème de Parra et Scheffler (1995). Nous donnons ici une preuve constructive de cette égalité. Plus précisément, nous proposons un algorithme qui étant donné un graphe $G$ de $n$ sommets et une décomposition arborescente de largeur $k$ de $G$, calcule en temps $O(n~k^3)$ une décomposition arborescente connexe de largeur $\leq k$ de $G$. Une conséquence importante de notre résultat est qu'il permet de borner par $\lceil\log{n}\rceil+1$ le rapport entre encerclement connexe et encerclement d'un réseau de $n$ noeuds.

Abstract

National audience

Additional details