{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:43:25Z","timestamp":1759063405673},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,6,11]],"date-time":"2011-06-11T00:00:00Z","timestamp":1307750400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,1]]},"DOI":"10.1007\/s00224-011-9339-2","type":"journal-article","created":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T12:09:38Z","timestamp":1307707778000},"page":"72-92","source":"Crossref","is-referenced-by-count":11,"title":["The Complexity of Flood Filling Games"],"prefix":"10.1007","volume":"50","author":[{"given":"Rapha\u00ebl","family":"Clifford","sequence":"first","affiliation":[]},{"given":"Markus","family":"Jalsenius","sequence":"additional","affiliation":[]},{"given":"Ashley","family":"Montanaro","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Sach","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,11]]},"reference":[{"key":"9339_CR1","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1006\/jctb.2001.2045","volume":"83","author":"E. Berger","year":"2001","unstructured":"Berger, E.: Dynamic monopolies of constant size. J. Comb. Theory, Ser. B 83, 191\u2013200 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9339_CR2","series-title":"MSRI Publications","first-page":"389","volume-title":"More Games of No Chance","author":"T.C. Biedl","year":"2002","unstructured":"Biedl, T.C., Demaine, E.D., Demaine, M.L., Fleischer, R., Jacobsen, L., Munro, J.I.: The complexity of Clickomania. In: More Games of No Chance. MSRI Publications, vol. 42, pp. 389\u2013404. Cambridge University Press, Cambridge (2002)"},{"issue":"4","key":"9339_CR3","doi-asserted-by":"crossref","first-page":"851","DOI":"10.2307\/3214517","volume":"30","author":"L. Chayes","year":"1993","unstructured":"Chayes, L., Winfield, C.: The density of interfaces: A new first-passage problem. J. Appl. Probab. 30(4), 851\u2013862 (1993)","journal-title":"J. Appl. Probab."},{"key":"9339_CR4","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/3-540-45071-8_36","volume-title":"Computing and Combinatorics","author":"E.D. Demaine","year":"2003","unstructured":"Demaine, E.D., Hohenberger, S., Liben-Nowell, D.: Tetris is hard, even to approximate. In: Computing and Combinatorics, pp. 351\u2013363 (2003)"},{"key":"9339_CR5","first-page":"178","volume-title":"Proc. Fun with Algorithms 2010","author":"R. Fleischer","year":"2010","unstructured":"Fleischer, R., Woeginger, G.: An algorithmic analysis of the Honey-Bee game. In: Proc. Fun with Algorithms 2010, pp. 178\u2013189 (2010)"},{"key":"9339_CR6","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S1570-8667(03)00022-4","volume":"1","author":"P. Flocchini","year":"2003","unstructured":"Flocchini, P., Kr\u00e1lovi\u010d, R., Ru\u017ei\u010dka, P., Roncato, A., Santoro, N.: On time versus size for monotone dynamic monopolies in regular topologies. J. Discrete Algorithms 1, 129\u2013150 (2003)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"9339_CR7","doi-asserted-by":"crossref","first-page":"746","DOI":"10.1214\/aoap\/1177005361","volume":"3","author":"L. Fontes","year":"1993","unstructured":"Fontes, L., Newman, C.: First passage percolation for random colorings of \u2124 d . Ann. Appl. Probab. 3(3), 746\u2013762 (1993)","journal-title":"Ann. Appl. Probab."},{"issue":"301","key":"9339_CR8","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"9339_CR9","unstructured":"Is this game NP-hard? (May 2009). http:\/\/valis.cs.uiuc.edu\/blog\/?p=2005"},{"issue":"2","key":"9339_CR10","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/s00224-008-9117-y","volume":"44","author":"K. Iwama","year":"2009","unstructured":"Iwama, K., Miyano, E., Ono, H.: Drawing borders efficiently. Theory Comput. Syst. 44(2), 230\u2013244 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"9339_CR11","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24(5), 1122\u20131139 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9339_CR12","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF03025367","volume":"22","author":"R. Kaye","year":"2000","unstructured":"Kaye, R.: Minesweeper is NP-complete. Math. Intell. 22(2), 9\u201315 (2000)","journal-title":"Math. Intell."},{"key":"9339_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4132-4","volume-title":"The Self-Avoiding Walk","author":"N. Madras","year":"1996","unstructured":"Madras, N., Slade, G.: The Self-Avoiding Walk. Birkh\u00e4user, Basel (1996)"},{"issue":"2","key":"9339_CR14","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"key":"9339_CR15","first-page":"133","volume-title":"Infectious Disease Modelling Research Progress","author":"P. Munz","year":"2009","unstructured":"Munz, P., Hudea, I., Imad, J., Smith, R.J.: When zombies attack!: Mathematical modelling of an outbreak of zombie infection. In: Infectious Disease Modelling Research Progress, pp. 133\u2013150. Nova Publ., New York (2009)"},{"key":"9339_CR16","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0166-218X(98)00043-2","volume":"86","author":"D. Peleg","year":"1998","unstructured":"Peleg, D.: Size bounds for dynamic monopolies. Discrete Appl. Math. 86, 263\u2013273 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9339_CR17","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K.-J. R\u00e4ih\u00e4","year":"1981","unstructured":"R\u00e4ih\u00e4, K.-J., Ukkonen, E.: The shortest common supersequence problem over binary alphabet is NP-complete. Theor. Comput. Sci. 16, 187\u2013198 (1981)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9339_CR18","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF01075212","volume":"25","author":"V.G. Timkovskii","year":"1989","unstructured":"Timkovskii, V.G.: Complexity of common subsequence and supersequence problems and related problems. Cybern. Syst. Anal. 25(5), 565\u2013580 (1989)","journal-title":"Cybern. Syst. Anal."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9339-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9339-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9339-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:23Z","timestamp":1558684463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9339-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,11]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["9339"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9339-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,11]]}}}