The complexity of flood-filling games on graphs

DOI10.1016/J.DAM.2011.09.001MaRDI QIDQ423894zbMATH OpenOpenAlexFDO

Authors Kitty Meeks, Alex 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) Games on graphs (graph-theoretic aspects) (05C57) Combinatorial games (91A46)

Recommendations

• The complexity of flood filling games
• The complexity of free-flood-it on \(2\times n\) boards
• Spanning trees and the complexity of flood-filling games
• Extremal properties of flood-filling games
• scientific article; zbMATH DE number 6399334

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• An algorithmic analysis of the Honey-Bee game
• The complexity of flood filling games
• The complexity of free-flood-it on \(2\times n\) boards
• The shortest common supersequence problem over binary alphabet is NP- complete

Cited in

(16)

• Flooding games on graphs
• On complexity of flooding games on graphs with interval representations
• How bad is the freedom to Flood-It?
• A Survey on the Complexity of Flood-Filling Games
• How Bad is the Freedom to Flood-It?
• Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
• The Flood-It game parameterized by the vertex cover number
• scientific article; zbMATH DE number 6399334 (Why is no real title available?)
• The complexity of free-flood-it on \(2\times n\) boards
• Spanning trees and the complexity of flood-filling games
• The complexity of flood filling games
• Extremal properties of flood-filling games
• Efficient approaches for the flooding problem on graphs
• Quell
• Parameterized complexity of flood-filling games on trees
• Tractability and hardness of flood-filling games on trees

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

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