The complexity of flood-filling games on graphs

DOI10.1016/J.DAM.2011.09.001zbMATH Open1239.05122OpenAlexW2031883007MaRDI QIDQ423894FDOQ423894

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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

Cited In (16)

• 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
• Title not available (Why is that?)
• The Flood-It game parameterized by the vertex cover number
• 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
• Flooding games on graphs

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)