Flooding games on graphs

Abstract : We study a discrete di usion process introduced in some combinatorial puzzles called Flood-It, Mad Virus or HoneyBee that can be played online and whose computational complexities have recently been studied. Originally defi ned on regular boards, we show that studying their dynamics directly on general graphs is valuable: we synthesize and extend previous results, we show how to solve Flood-It on cycles by computing a poset height and how to solve the 2-Free-Flood-It variant by computing a graph radius (ENGLISH VERSION of [11])
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2014, LAGOS’11, Part 2, 164, pp.532-538. 〈10.1016/j.dam.2013.09.024〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00653714
Contributeur : Eric Thierry <>
Soumis le : mardi 20 décembre 2011 - 09:14:46
Dernière modification le : mardi 16 janvier 2018 - 15:35:39
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 16:05:48

Fichier

FLOODS-DAM.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Aurélie Lagoutte, Mathilde Noual, Eric Thierry. Flooding games on graphs. Discrete Applied Mathematics, Elsevier, 2014, LAGOS’11, Part 2, 164, pp.532-538. 〈10.1016/j.dam.2013.09.024〉. 〈hal-00653714〉

Partager

Métriques

Consultations de la notice

442

Téléchargements de fichiers

217