Geodesic
Extremal properties of flood-filling games
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4.

Voir la notice de l'article provenant de la source Episciences

The problem of determining the number of "flooding operations" required to make a given coloured graph monochromatic in the one-player combinatorial game Flood-It has been studied extensively from an algorithmic point of view, but basic questions about the maximum number of moves that might be required in the worst case remain unanswered. We begin a systematic investigation of such questions, with the goal of determining, for a given graph, the maximum number of moves that may be required, taken over all possible colourings. We give several upper and lower bounds on this quantity for arbitrary graphs and show that all of the bounds are tight for trees; we also investigate how much the upper bounds can be improved if we restrict our attention to graphs with higher edge-density. 
@article{DMTCS_2019_21_4_a3,
     author = {Meeks, Kitty and Vu, Dominik K.},
     title = {Extremal properties of flood-filling games},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2019},
     doi = {10.23638/DMTCS-21-4-11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-11/}
}
TY  - JOUR
AU  - Meeks, Kitty
AU  - Vu, Dominik K.
TI  - Extremal properties of flood-filling games
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-11/
DO  - 10.23638/DMTCS-21-4-11
LA  - en
ID  - DMTCS_2019_21_4_a3
ER  - 
%0 Journal Article
%A Meeks, Kitty
%A Vu, Dominik K.
%T Extremal properties of flood-filling games
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-11/
%R 10.23638/DMTCS-21-4-11
%G en
%F DMTCS_2019_21_4_a3
Meeks, Kitty; Vu, Dominik K. Extremal properties of flood-filling games. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi : 10.23638/DMTCS-21-4-11. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-11/

Cité par Sources :