The complexity of flood filling games
From MaRDI portal
Publication:692938
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
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.