Journal article icon

Journal article

Spanning trees and the complexity of flood-filling games

Abstract:

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 p...

Expand abstract

Actions


Access Document


Authors


Journal:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume:
7288 LNCS
Pages:
282-292
Publication date:
2012
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:d00b7ae3-1c8d-4a8b-9549-6b0abaf9939f
Source identifiers:
395905
Local pid:
pubs:395905
Language:
English

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP