Flooding games on graphs

Aurélie Lagoutte (1, 2) , Mathilde Noual (1, 3, 2) , Eric Thierry (1, 2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 MC2 - Modèles de calcul, Complexité, Combinatoire
3 IXXI - Institut Rhône-Alpin des systèmes complexes

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])

Domaines: Complexité [cs.CC]; Combinatoire [math.CO]

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