Evènement pour le groupe GT Graphes et Applications

Date 2010-10-01  14:00-15:00
TitreSurveillance de réseaux éléctriques, Power Domination 
Résumé Power domination was introduced by Haynes et al as a graph theoretical description of a physical problem. The initial problem, proposed by Baldwin et al was to monitor an electrical network by placing as few phase measurement units as possible. A phase measurement unit placed on a vertex of a graph permits to monitor all the vertices of its closed neighborhood. Then, thanks to Kirschoff laws, any monitored vertex adjacent to only one unmonitored vertex allows to also monitor this neighbour. With these rules, a power dominating set is a set of vertices that allows to monitor the whole graph. The power domination number is the minimum cardinality of a power dominating set. This definition of the problem induces some propagation phenomenon that is uncommon in domination problems, and looks more like the behaviour of some life game. For exemple, the power domination of a path is only one, however long the path is. During this talk, we shall present a common generalization of domination and power domination, denoted k-power domination. In this variant, a monitored vertex adjacent to at most k unmonitored neighbours allows to have these neighbours monitored. When k=1, this is the power domination, and usual domination corresponds to the case when k=0. Surprisingly, studying this new variant, we managed to extend some classical domination results to k-power domination, like for exemple a linear algorithm for trees very different from the algorithm proposed by Haynes et al. We also extended various results of power domination to k-power domination.  
LieuSalle 178 
OrateurPaul Dorbec 

Aucun document lié à cet événement.

Retour à l'index