Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 29 Janvier 2019

Le jeu de domination dans les graphes

par Paul Dorbec (GREYC, Caen)

Comme cela avait été fait depuis longtemps pour la coloration, un jeu de domination a été proposé en 2010. Deux joueurs jouent tour à tour sur un graphe. Chaque coup consiste à sélectionner un sommet et à ajouter ses voisins à l'ensemble des sommets dominés du graphe, initialement vide. Un coup n'est légal que s'il accroit effectivement l'ensemble des sommets dominés. Lorsque le graphe est entièrement dominé et donc qu'aucun coup restant n'est légal, on définit le score de la partie par le nombre de coups joués conjointement, c'est-à-dire la taille de l'ensemble dominant du graphe construit.

Les joueurs ont des objectifs antagonistes, Dominator veut minimiser le score et Staller s'évertue à le maximiser. Le nombre de domination ludique d'un graphe est le score obtenu lorsque les deux joueurs jouent de façon optimale. Deux variantes du paramètres sont étudiées, selon qui ouvre le jeu. Nous nous intéresserons à quelques résultats généraux sur le problème, notamment sur les graphes présentant des propriétés spécifiques pour ce jeu, et aux liens entre les deux variantes.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr