Skip to Main content Skip to Navigation
Journal articles

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])
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/hal-00653714
Contributor : Eric Thierry <>
Submitted on : Tuesday, December 20, 2011 - 9:14:46 AM
Last modification on : Wednesday, July 8, 2020 - 12:43:07 PM
Document(s) archivé(s) le : Friday, November 16, 2012 - 4:05:48 PM

File

FLOODS-DAM.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

705

Files downloads

355