Evènement pour le groupe GT Graphes et Applications


Date 2016-01-08  14:00-15:00
TitrePower domination in triangulations 
RésuméLa domination de puissance dans les graphes est un problème qui provient de problèmes de surveillance dans les réseaux électriques. Le but de la domination de puissance est de surveiller tous les sommets d'un graphe donné, à l'aide d'un ensemble S de capteurs. On note M l'ensemble des sommets surveillés. La domination de puissance utilise le processus suivant: - On place des sommets dans un ensemble initial S - (domination) les sommets de S et leurs voisins sont ajoutés à M - (propagation) un sommet de M se "propage" vers un voisin si c'est son seul voisin qui n'appartient pas à M. Ce voisin est ajouté à M. L'étape de propagation se répète tant qu'on trouve un sommet à propager. On dit que S est un emph{ensemble de domination de puissance} si M contient tous les sommets du graphe à la fin du processus. Le emph{nombre de domination de puissance} de G, noté $gamma_P(G)$, est la taille minimum de S. Le problème de détermination de $gamma_P(G)$ pour un graphe donné a été prouvé NP-complet pour les graphes planaires. Un des obstacles à l'étape de propagation dans les graphes est la présence de certains sommets d'articulation. Nous nous intéressons donc naturellement aux triangulations (graphes dans lesquels toutes les faces sont de degré 3) car elles ne contiennent pas de tels sommets. Nous présentons une preuve que $gamma_P(G) leq dfrac{n-2}{4}$ si $G$ est une triangulation à $n geq 6$ sommets.  
LieuSalle 178 
OrateurClaire Pennarun 



Aucun document lié à cet événement.

Retour
Retour à l'index