Flooding games on graphs

DOI10.1016/j.dam.2013.09.024zbMath1288.05175OpenAlexW1981014315MaRDI QIDQ2448890

Mathilde Noual, Aurélie Lagoutte, Éric 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

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

Related Items (8)

Unnamed Item ⋮ The Flood-It game parameterized by the vertex cover number ⋮ Efficient approaches for the flooding problem on graphs ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ How Bad is the Freedom to Flood-It? ⋮ 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

• The complexity of free-flood-it on \(2\times n\) boards
• The complexity of flood-filling games on graphs
• The complexity of flood filling games
• An algorithmic analysis of the Honey-Bee game
• On the complexity of loop fusion
• On Complexity of Flooding Games on Graphs with Interval Representations
• Unnamed Item
• Unnamed Item

This page was built for publication: Flooding games on graphs