A probabilistic version of the game of Zombies and Survivors on graphs

Abstract : We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is at least 1/2. We present asymptotic results for the zombie numbers of several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and Cartesian and toroidal grids.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, 〈10.1016/j.tcs.2015.12.012〉
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01291964
Contributeur : Dieter Mitsche <>
Soumis le : mardi 22 mars 2016 - 12:58:37
Dernière modification le : mercredi 10 octobre 2018 - 21:46:01
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 22:41:30

Fichier

zombies.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Anthony Bonato, Dieter Mitsche, Xavier Pérez-Giménez, Pawel Pralat. A probabilistic version of the game of Zombies and Survivors on graphs. Theoretical Computer Science, Elsevier, 2015, 〈10.1016/j.tcs.2015.12.012〉. 〈hal-01291964〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

24