Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
type: Item
instance of: scholarly article
title: Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
zbMATH Open document ID: 1387.05197
author: Fábio Protti
author: Maise Dantas da Silva
author: Uéverton S. Souza
author: Michael R. Fellows
author: Frances Rosamond
published in: Discrete Applied Mathematics
publication date: 2018-05-24T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C57
zbMATH DE Number: 6872412
zbMATH Keywords: Flood-It
zbMATH Keywords: flood-filling
zbMATH Keywords: vertex cover
zbMATH Keywords: FPT
zbMATH Keywords: kernel
zbMATH Keywords: ETH
MaRDI profile type: Publication
full work available at URL: j.dam.2017.07.004
OpenAlex ID: W2744836120
cites work: On problems without polynomial kernels
cites work: (Meta) Kernelization
cites work: Kernel bounds for path and cycle problems
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Kernel bounds for disjoint cycles and disjoint paths
cites work: The complexity of flood filling games
cites work: Parameterized Algorithms
cites work: Incompressibility through Colors and IDs
cites work: Q4503944
cites work: Tractability and hardness of flood-filling games on trees
cites work: Analogs & duals of the MAST problem for sequences & trees
cites work: An algorithmic analysis of the Honey-Bee game
cites work: Q3549693
cites work: Q4198056
cites work: Which problems have strongly exponential complexity?
cites work: Flooding games on graphs
cites work: Algorithmic meta-theorems for restrictions of treewidth
cites work: The complexity of flood-filling games on graphs
cites work: The complexity of free-flood-it on \(2\times n\) boards
cites work: Spanning trees and the complexity of flood-filling games
cites work: Lower bounds on kernelization
cites work: Ramsey numbers and an approximation algorithm for the vertex cover problem
cites work: The consensus string problem for a metric is NP-complete
cites work: Parameterized Complexity of Flood-Filling Games on Trees
cites work: Q5173160
DOI: 10.1016/J.DAM.2017.07.004
description: scientific article; zbMATH DE number 6872412