Fractional Combinatorial Games on Graphs

Ronan Pardo Soares 1, 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : De nombreux jeux impliquant deux joueurs dans un graphe ont été étudiés en théorie des graphes, par exemple: Gendarmes et voleur, Ange et Démon, Observeur et surfeur, Dominants universels, etc. Outre la capture d'un fugitif ou la lutte contre le feu, ces jeux ont aussi des applications dans les réseaux de télécommunications car, d'une part, ils permettent de mieux appréhender les structures des réseaux, et d'autre part, ils permettent de modéliser et d'étudier des problèmes de ces réseaux (e.g., problème de cache dans l'internet). Dans tous ces jeux, chaque joueur contrôle des jetons sur les sommets du graphe et selon les jeux, les joueurs peuvent: déplacer des jetons le long des arêtes du graphe, ajouter/supprimer des jetons, etc. Dans ce travail, nous proposons une approche générale en définissant un jeu qui constitue, entre autre, une relaxation fractionnaire de tous les jeux mentionnés ci-dessus. Pour ce jeu générique, nous montrons qu'il existe un algorithme en temps polynomial, en le nombre de sommets du graphe et le nombre de maximum de tours de jeu autorisés, pour décider si un des joueurs a une stratégie gagnante. Entre autre, cet algorithme permet d'avoir une stratégie gagnante, avec forte probabilité, pour le problème de cache.
Type de document :
Communication dans un congrès
Nisse, Nicolas and Rousseau, Franck and Busnel, Yann. 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2013, Pornic, France. 2013
Liste complète des métadonnées

https://hal.inria.fr/hal-00813229
Contributeur : Ronan Pardo Soares <>
Soumis le : mardi 16 avril 2013 - 15:20:26
Dernière modification le : mercredi 7 octobre 2015 - 01:15:05
Document(s) archivé(s) le : mercredi 17 juillet 2013 - 04:05:34

Fichier

FractionalGamesSurveillance-Su...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00813229, version 2

Collections

Citation

Ronan Pardo Soares. Fractional Combinatorial Games on Graphs. Nisse, Nicolas and Rousseau, Franck and Busnel, Yann. 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2013, Pornic, France. 2013. <hal-00813229v2>

Partager

Métriques

Consultations de
la notice

183

Téléchargements du document

96