Flooding games on graphs

DOI10.1016/J.DAM.2013.09.024MaRDI QIDQ2448890zbMATH OpenOpenAlexFDO

Authors A. Lagoutte, Mathilde Noual, Eric Thierry

Publication date 5 May 2014

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

Full work available at URL https://hal.inria.fr/hal-00653714/file/FLOODS-DAM.pdf

zbMATH Keywords

colored graphcombinatorial puzzleneighborhood contraction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Combinatorial games (91A46)

Recommendations

• The complexity of flood-filling games on graphs
• On complexity of flooding games on graphs with interval representations
• The complexity of flood filling games
• Spanning trees and the complexity of flood-filling games
• Extremal properties of flood-filling games
• A Survey on the Complexity of Flood-Filling Games
• Games on graphs

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An algorithmic analysis of the Honey-Bee game
• On complexity of flooding games on graphs with interval representations
• On the complexity of loop fusion
• The complexity of flood filling games
• The complexity of flood-filling games on graphs
• The complexity of free-flood-it on \(2\times n\) boards

Cited in

(11)

• 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?
• scientific article; zbMATH DE number 7556143 (Why is no real title available?)
• 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
• Spanning trees and the complexity of flood-filling games
• Extremal properties of flood-filling games
• Efficient approaches for the flooding problem on graphs
• Tractability and hardness of flood-filling games on trees

This page was built for publication: Flooding games on graphs

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