The complexity of flood filling games

DOI10.1007/s00224-011-9339-2zbMath1253.68146arXiv1001.4420OpenAlexW2126364564WikidataQ58478282 ScholiaQ58478282MaRDI QIDQ692938

Ashley Montanaro, Markus Jalsenius, Benjamin Sach, Raphaël Clifford

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1001.4420

zbMATH Keywords

percolationNP-completenesscombinatorial gamesflood-filling

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

Related Items

Unnamed Item ⋮ The Flood-It game parameterized by the vertex cover number ⋮ Efficient approaches for the flooding problem on graphs ⋮ The complexity of free-flood-it on \(2\times n\) boards ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ The complexity of flood-filling games on graphs ⋮ How Bad is the Freedom to Flood-It? ⋮ Flooding games on graphs ⋮ Spanning trees and the complexity of flood-filling games ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Tractability and hardness of flood-filling games on trees

Cites Work

• Unnamed Item
• Unnamed Item
• The shortest common supersequence problem over binary alphabet is NP- complete
• Size bounds for dynamic monopolies
• First passage percolation for random colorings of \(\mathbb{Z}^ d\)
• On time versus size for monotone dynamic monopolies in regular topologies
• Dynamic monopolies of constant size
• Drawing borders efficiently
• Tetris is Hard, Even to Approximate
• The Complexity of Some Problems on Subsequences and Supersequences
• The density of interfaces: a new first-passage problem
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Probability Inequalities for Sums of Bounded Random Variables
• Minesweeper is NP-complete.