The Complexity of Free Flood Filling Games

概要

論文の詳細を見る
The flood filling games on a graph is a kind of graph coloring game. The one player version of the game is known as Flood-It, and the two player version is known as Honey-Bee Game. We consider the case that the player can color arbitrary vertex. This version is called free flood filling game. We concentrate at the one player version of the free flood filling game on a graph. In this paper, we show that the free Flood-It is NP-complete on trees with only three colors, and it is polynomial time solvable on paths and cycles with any number of colors.
2011-08-30