Computer Science – Data Structures and Algorithms
Scientific paper
2011-01-31
Computer Science
Data Structures and Algorithms
More typos corrected!
Scientific paper
10.1016/j.dam.2011.09.001
We consider the complexity of problems related to the combinatorial game Free-Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. Although computing the minimum number of moves required to flood an arbitrary graph is known to be NP-hard, we demonstrate a polynomial time algorithm to compute the minimum number of moves required to link each pair of vertices. We apply this result to compute in polynomial time the minimum number of moves required to flood a path, and an additive approximation to this quantity for an arbitrary k x n board, coloured with a bounded number of colours, for any fixed k. On the other hand, we show that, for k>=3, determining the minimum number of moves required to flood a k x n board coloured with at least four colours remains NP-hard.
Meeks Kitty
Scott Alexander
No associations
LandOfFree
The complexity of flood-filling games on graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The complexity of flood-filling games on graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of flood-filling games on graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647243