LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Meeks, Kitty; Scott, Alexander (2012)
Publisher: Springer Verlag
Languages: English
Types: Article
Subjects: QA, Computer Science - Data Structures and Algorithms, QA75
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 \ud 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Flood It Game, http:// oodit.appspot.com.
    • [2] Flood It! 2, available at http://itunes.apple.com.
    • [3] Flood It!, available at https://market.android.com.
    • [4] Mad Virus, http://www.bubblebox.com/play/puzzle/539.htm.
    • [5] David Arthur, Raphael Cli ord, Markus Jalsenius, Ashley Montanaro, and Benjamin Sach, The Complexity of Flood Filling Games, in Paolo Boldi and Luisa Gargano, editors, FUN, volume 6099 of Lecture Notes in Computer Science, Springer, ISBN 978-3-642-13121-9, 2010, pages 307-318.
    • [6] A. Born, Flash application Biene (Honey-Bee), 2009. graz.ac.at/Bugs/htm/games/biene.htm.
    • [7] Raphael Cli ord, Markus Jalsenius, Ashley Montanaro, and Benjamin Sach, The Complexity of Flood Filling Games, arXiv.1001.4420v2 [cs.DS], August 2010.
    • [8] Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1990.
    • [9] Rudolf Fleischer and Gerard J. Woeginger, An Algorithmic Analysis of the Honey-Bee Game, in Paolo Boldi and Luisa Gargano, editors, FUN, volume 6099 of Lecture Notes in Computer Science, Springer, ISBN 978- 3-642-13121-9, 2010, pages 178-189.
    • [10] H. Fukui, A. Nakanishi, R. Uehara, T. Uno, Y. Uno, The complexity of free ooding games, Information Processing Society of Jamap (IPSG) SIG Notes 2011 (August 2011), 1-5.
    • [11] Aurelie Lagoutte, Jeux d'inondation dans les graphes, Technical report, ENS Lyon, HAL: hal-00509488, August 2010.
    • [12] A. Lagoutte, M. Noual, E. Thierry, Flooding games on graphs, HAL: hal-00653714, December 2011.
    • [13] Kitty Meeks and Alexander Scott, The complexity of oodlling games on graphs, Discrete Applied Mathematics (2011), doi:10.1016/j.dam.2011.09.001.
    • [14] Kitty Meeks and Alexander Scott, The complexity of Free-Flood-It on 2 n boards, arxiv.1101.5518v1 [cs.DS], January 2011.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article