Spanning trees and the complexity of flood-filling games

Details Spanning trees and the complexity of flood-filling games Spanning trees and the complexity of flood-filling games

2012-03-12

arxiv.org/abs/1203.2538v1

Computer Science

Data Structures and Algorithms

29 pages

Scientific paper

We consider 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. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.

Affiliated with

Also associated with

No associations

Rating

Spanning trees and the complexity of flood-filling games 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 Spanning trees and the complexity of flood-filling games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning trees and the complexity of flood-filling games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488640