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 : jeudi 12 juillet 2018 - 01:04:57
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

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

587

Téléchargements de fichiers

237