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

Content Provider	Semantic Scholar
Author	Fraigniaud, Pierre Nisse, Nicolas
Copyright Year	2005
Abstract	Le probleme de l'encerclement dans les reseaux a ete introduit par Parson (1976) : etant donne un reseau ``contamine'' (par exemple dans lequel un intrus s'est introduit), l'emph{encerclement} du reseau est le nombre minimum d'agents necessaires pour ``nettoyer'' le reseau (c'est-a-dire capturer l'intrus). Une strategie d'encerclement est dite connexe si a chaque etape de la strategie, l'ensemble des liens nettoyes induit un sous-reseau connexe. Les strategies d'encerclement connexes sont essentielles si l'on souhaite assurer des communications sures entre les agents. Dans le cas des reseaux en arbres, Barriere {sl et al.} (2002, 2003) ont prouve que le rapport entre l'encerclement connexe et l'encerclement est majore par 2, et que cette borne est optimale. Dans cet article, nous donnons une borne pour ce rapport dans le cas des reseaux arbitraires. Pour cela nous utilisons une notion cruciale de theorie des graphes : la largeur arborescente. L'egalite entre la largeur arborescente connexe d'un graphe et sa largeur arborescente decoule du theoreme de Parra et Scheffler (1995). Nous donnons ici une preuve constructive de cette egalite. Plus precisement, nous proposons un algorithme qui etant donne un graphe $G$ de $n$ sommets et une decomposition arborescente de largeur $k$ de $G$, calcule en temps $O(n~k^3)$ une decomposition arborescente connexe de largeur $\leq k$ de $G$. Une consequence importante de notre resultat est qu'il permet de borner par $\lceil\log{n}\rceil+1$ le rapport entre encerclement connexe et encerclement d'un reseau de $n$ noeuds.
Starting Page	13
Ending Page	16
Page Count	4
File Format	PDF HTM / HTML
Alternate Webpage(s)	http://www-sop.inria.fr/mascotte/Events/Algotel2005/Actes/02.pdf
Alternate Webpage(s)	http://www-sop.inria.fr/mascotte/Algotel2005/Actes/02.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article