The complexity of flood-filling games on graphs

DOI10.1016/j.dam.2011.09.001zbMath1239.05122OpenAlexW2031883007MaRDI QIDQ423894

Kitty Meeks, Alexander D. Scott

Publication date: 30 May 2012

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

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

zbMATH Keywords

computational complexitygraph colouring

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial games (91A46) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (10)

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 ⋮ 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
• The complexity of free-flood-it on \(2\times n\) boards
• The complexity of flood filling games
• An algorithmic analysis of the Honey-Bee game
• The shortest common supersequence problem over binary alphabet is NP- complete

This page was built for publication: The complexity of flood-filling games on graphs