Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

The Flood-It game parameterized by the vertex cover number

Souza, Uéverton dos Santos, Rosamond, Frances, Fellows, Michael R., Protti, Fabio and da Silva, Maise Dantas (2015). The Flood-It game parameterized by the vertex cover number. Electronic Notes in Discrete Mathematics,50(December 2015):35-40.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 81144320xPUB197
Title The Flood-It game parameterized by the vertex cover number
Author Souza, Uéverton dos Santos
Rosamond, Frances
Fellows, Michael R.
Protti, Fabio
da Silva, Maise Dantas
Journal Name Electronic Notes in Discrete Mathematics
Publication Date 2015
Volume Number 50
Issue Number December 2015
ISSN 1571-0653   (check CDU catalogue  open catalogue search in new window)
Scopus ID 2-s2.0-84953373346
Start Page 35
End Page 40
Total Pages 6
Place of Publication Netherlands
Publisher Elsevier BV
Field of Research ENGINEERING
HERDC Category C1 - Journal Article (DIISR)
Abstract Flood-It is a combinatorial problem on a colored graph whose aim is to make the graph monochromatic using the minimum number of flooding moves, relatively to a pivot vertex p. A flooding move consists of changing the color of the monochromatic component (maximal monochromatic connected subgraph) containing p. This problem generalizes a combinatorial game named alike which is played on m×n grids. It is known that Flood-It remains NP-hard even for 3×n grids and for instances with bounded number of colors, diameter, or treewidth. In contrast, in this work we show that Flood-It is fixed-parameter tractable when parameterized by the vertex cover number, and admits a polynomial kernelization when, besides the vertex cover number, the number of colors is an additional parameter.
Keywords Flood-It
fixed-parameter tractability
polynomial kernelization
DOI http://dx.doi.org/10.1016/j.endm.2015.07.007   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 4 Abstract Views  -  Detailed Statistics
Created: Tue, 26 Jul 2016, 12:41:50 CST