An algorithmic analysis of Flood-It and Free-Flood-It on graph powers

Abstract : Flood-it is a combinatorial game played on a colored graph G whose aim is to make the graph monochromatic using the minimum number of flooding moves, relatively to a fixed pivot. Free-Flood-it is a variant where the pivot can be freely chosen for each move of the game. The standard versions of Flood-it and Free-Flood-it are played on m ×n grids. In this paper we analyze the behavior of these games when played on other classes of graphs, such as d-boards, powers of cycles and circular grids. We describe polynomial time algorithms to play Flood-it on C2n (the second power of a cycle on n vertices), 2 ×n circular grids, and some types of d-boards (grids with a monochromatic column). We also show that Free-Flood-it is NP-hard on C2n and 2 ×n circular grids.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.279--290
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01188900
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:07
Dernière modification le : lundi 11 décembre 2017 - 17:36:01
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:41:40

Fichier

dmtcs-16-3-16.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188900, version 1

Collections

Citation

Uéverton dos Santos Souza, Fábio Protti, Maise Silva. An algorithmic analysis of Flood-It and Free-Flood-It on graph powers. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.279--290. 〈hal-01188900〉

Partager

Métriques

Consultations de la notice

71

Téléchargements de fichiers

227