Fractional Combinatorial Games on Graphs

Ronan Pardo Soares 1, 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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.
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/hal-00813229
Contributor : Ronan Pardo Soares <>
Submitted on : Tuesday, April 16, 2013 - 3:20:26 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Wednesday, July 17, 2013 - 4:05:34 AM

File

FractionalGamesSurveillance-Su...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00813229, version 2

Collections

Citation

Ronan Pardo Soares. Fractional Combinatorial Games on Graphs. 15èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), May 2013, Pornic, France. ⟨hal-00813229v2⟩

Share

Metrics

Record views

283

Files downloads

134