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


Journal:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) More from this journal
Volume:
7288 LNCS
Pages:
282-292
Publication date:
2012-01-01
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
Language:
English
Pubs id:
pubs:395905
UUID:
uuid:d00b7ae3-1c8d-4a8b-9549-6b0abaf9939f
Local pid:
pubs:395905
Source identifiers:
395905
Deposit date:
2013-11-17

Terms of use


Views and Downloads






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

TO TOP