From LaBRI - Laboratoire Bordelais de Recherche en Informatique

Theses: 2013Dorbec

Domination de puissance

La domination de puissance est une variante de la domination dans les graphes issue d'un problème de surveillance de réseau électrique. Il s'agit de choisir un ensemble initial de sommets où placer des unités de mesure pour surveiller tout le graphe. Tout sommet voisin d'une unité de mesure est surveillé initialement. Puis une procédure itérative permet d'étendre l'ensemble des sommets dominés. On cherche un ensemble initial minimum qui surveille tout le graphe. Le problème est récent et très prometteur, au vu de la dynamique sur le sujet. La majeure partie de l'activité existante sur le sujet traite de la complexité algorithmique du problème et de ses variantes. L'analyse en termes de bornes et classes de graphes reste assez inexplorée. Le sujet de la thèse porte sur cette analyse, en particulier dans les produits de graphes. On explorera aussi deux variantes de la domination de puissance dans les familles de graphes usuelles.

Récupéré sur http://www.labri.fr/index.php?n=Theses.2013Dorbec
Page mise à jour le 10/06/2013 à 15:29