Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number

DOI10.1016/J.DAM.2017.07.004MaRDI QIDQ1752485zbMATH OpenOpenAlexFDO

Authors Fábio Protti, Maise Dantas da Silva, Uéverton S. Souza, Michael R. Fellows, Frances Rosamond

Publication date 24 May 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2017.07.004

zbMATH Keywords

ETHflood-fillingFlood-ItFPTkernelvertex cover

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The Flood-It game parameterized by the vertex cover number
• Parameterized complexity of flood-filling games on trees
• The complexity of flood-filling games on graphs
• Tractability and hardness of flood-filling games on trees
• The complexity of flood filling games

Cites work

• (Meta) Kernelization
• Algorithmic meta-theorems for restrictions of treewidth
• An algorithmic analysis of the Honey-Bee game
• Analogs & duals of the MAST problem for sequences & trees
• Flooding games on graphs
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel bounds for path and cycle problems
• Kernelization Lower Bounds by Cross-Composition
• Lower bounds on kernelization
• On problems without polynomial kernels
• Parameterized algorithms
• Parameterized complexity of flood-filling games on trees
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Spanning trees and the complexity of flood-filling games
• The complexity of flood filling games
• The complexity of flood-filling games on graphs
• The complexity of free-flood-it on \(2\times n\) boards
• The consensus string problem for a metric is NP-complete
• Tractability and hardness of flood-filling games on trees
• Which problems have strongly exponential complexity?

Cited in

(5)

• The Flood-It game parameterized by the vertex cover number
• The complexity of free-flood-it on \(2\times n\) boards
• How Bad is the Freedom to Flood-It?
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• A Survey on the Complexity of Flood-Filling Games

This page was built for publication: Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1752485)