{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:19:59Z","timestamp":1742962799135,"version":"3.40.3"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319983547"},{"type":"electronic","value":"9783319983554"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_20","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"357-376","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Survey on the Complexity of Flood-Filling Games"],"prefix":"10.1007","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maise","family":"Dantas da Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"U\u00e9verton S.","family":"Souza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-642-13122-6_30","volume-title":"Fun with Algorithms","author":"D Arthur","year":"2010","unstructured":"Arthur, D., Clifford, R., Jalsenius, M., Montanaro, A., Sach, B.: The complexity of flood filling games. In: Boldi, P., Gargano, L. (eds.) FUN 2010. LNCS, vol. 6099, pp. 307\u2013318. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13122-6_30"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Aschwanden, C.: Spatial simulation model for infectious viral disease with focus on sars and the common flu. In: 37th Annual Hawaii International Conference on System Sciences, HICSS (2004)","DOI":"10.1109\/HICSS.2004.1265357"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Barone, P., Bonizzoni, P., Vedova, G.D., Mauri, G.: An approximation algorithm for the shortest common supersequence problem: an experimental analysis. In: ACM Symposium on Applied, Computing, pp. 56\u201360 (2001)","DOI":"10.1145\/372202.372275"},{"key":"20_CR4","first-page":"23","volume":"17","author":"K Becker","year":"2001","unstructured":"Becker, K.: Teaching with games: the minesweeper and asteroids experience. J. Comput. Sci. Coll. 17, 23\u201333 (2001)","journal-title":"J. Comput. Sci. Coll."},{"key":"20_CR5","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","volume":"244","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T., Wareham, T., Warnow, T.: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs. Theor. Comput. Sci. 244, 167\u2013188 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-540-73545-8_10","volume-title":"Computing and Combinatorics","author":"B Chor","year":"2007","unstructured":"Chor, B., Fellows, M., Ragan, M.A., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, pp. 75\u201385. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73545-8_10"},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/s00224-011-9339-2","volume":"50","author":"R Clifford","year":"2012","unstructured":"Clifford, R., Jalsenius, M., Montanaro, A., Sach, B.: The complexity of flood-filling games. Theory Comput. Syst. 50(1), 72\u201392 (2012)","journal-title":"Theory Comput. Syst."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"dos Santos Souza, U., Rosamond, F., Fellows, M.R., Protti, F., da Silva, M.D.: The flood-it game parameterized by the vertex cover number. In: LAGOS 2015 - VIII Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 50, pp. 35\u201340 (2015)","DOI":"10.1016\/j.endm.2015.07.007"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-73420-8_31","volume-title":"Automata, Languages and Programming","author":"MR Fellows","year":"2007","unstructured":"Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 340\u2013351. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73420-8_31"},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0196-6774(03)00081-6","volume":"49","author":"MR Fellows","year":"2003","unstructured":"Fellows, M.R., Hallett, M.T., Stege, U.: Analogs and duals of the mast problem for sequences and trees. J. Algorithms 49(1), 192\u2013216 (2003)","journal-title":"J. Algorithms"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/3-540-57273-2_52","volume-title":"Algorithms\u2014ESA 1993","author":"MR Fellows","year":"1993","unstructured":"Fellows, M.R., Hallett, M.T., Wareham, H.T.: DNA physical mapping: three ways difficult. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol. 726, pp. 157\u2013168. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-57273-2_52"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Fellows, M., Protti, F., Rosamond, F., da Silva, M.D., Souza, U.S.: Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number. Discrete Appl. Math. 245, 94\u2013100 (2017)","DOI":"10.1016\/j.dam.2017.07.004"},{"key":"20_CR13","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.tcs.2015.02.008","volume":"576","author":"MR Fellows","year":"2015","unstructured":"Fellows, M.R., dos Santos Souza, U., Protti, F., da Silva, M.D.: Tractability and hardness of flood-filling games on trees. Theor. Comput. Sci. 576, 102\u2013116 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/978-3-642-13122-6_19","volume-title":"Fun with Algorithms","author":"R Fleischer","year":"2010","unstructured":"Fleischer, R., Woeginger, G.J.: An algorithmic analysis of the honey-bee game. In: Boldi, P., Gargano, L. (eds.) FUN 2010. LNCS, vol. 6099, pp. 178\u2013189. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13122-6_19"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-45281-9_7","volume-title":"Computational Geometry and Graphs","author":"H Fukui","year":"2013","unstructured":"Fukui, H., Otachi, Y., Uehara, R., Uno, T., Uno, Y.: On complexity of flooding games on graphs with interval representations. In: Akiyama, J., Kano, M., Sakai, T. (eds.) TJJCCGG 2012. LNCS, vol. 8296, pp. 73\u201384. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45281-9_7"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M Golumbic","year":"1994","unstructured":"Golumbic, M., Kaplan, H., Shamir, R.: On the complexity of dna physical mapping. Adv. Appl. Math. 15, 251\u2013261 (1994)","journal-title":"Adv. Appl. Math."},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D Gusfield","year":"1981","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary tree. Networks 21, 19\u201328 (1981)","journal-title":"Networks"},{"key":"20_CR18","unstructured":"Hallett, M.T.: An integrated complexity analysis of problems from computational biology. Ph.D. thesis, University of Victoria (1996)"},{"key":"20_CR19","unstructured":"Hon, W.-K., Kloks, T., Liu, F.-H., Liu, H.-H., Wang, H.-L.: Flood-it on at-free graphs. arXiv preprint arXiv:1511.01806 (2015)"},{"key":"20_CR20","first-page":"112","volume":"115","author":"J Hromkovi\u010d","year":"2015","unstructured":"Hromkovi\u010d, J.: Homo informaticus: why computer science fundamentals are an unavoidable part of human culture and how to teach them. Bull. EATCS 115, 112\u2013122 (2015)","journal-title":"Bull. EATCS"},{"key":"20_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-71483-7_1","volume-title":"Informatics in Schools: Focus on Learning Programming","author":"J Hromkovi\u010d","year":"2017","unstructured":"Hromkovi\u010d, J., Lacher, R.: The Computer science way of thinking in human history and consequences for the design of computer science curricula. In: Dagiene, V., Hellas, A. (eds.) ISSEP 2017. LNCS, vol. 10696, pp. 3\u201311. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-71483-7_1"},{"key":"20_CR22","unstructured":"Hromkovic, J., Kohn, T., Komm, D., Serafini, G.: Algorithmic thinking from the start. In: The Education Column, Bulletin of the EATCS, p. 121 (2017)"},{"key":"20_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-319-71483-7_18","volume-title":"Informatics in Schools: Focus on Learning Programming","author":"J Hromkovi\u010d","year":"2017","unstructured":"Hromkovi\u010d, J., Serafini, G., Staub, J.: XLogoOnline: a single-page, browser-based programming environment for schools aiming at reducing cognitive load on pupils. In: Dagiene, V., Hellas, A. (eds.) ISSEP 2017. LNCS, vol. 10696, pp. 219\u2013231. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-71483-7_18"},{"issue":"4","key":"20_CR24","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TCBB.2006.55","volume":"3","author":"V Lacroix","year":"2006","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.F.: Motif search in graphs: application to metabolic networks. IEEE\/ACM Trans. Comput. Biol. Bioinf. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"20_CR25","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.dam.2013.09.024","volume":"164","author":"A Lagoutte","year":"2014","unstructured":"Lagoutte, A., Noual, M., Thierry, E.: Flooding games on graphs. Discrete Appl. Math. 164, 532\u2013538 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"20_CR26","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00453-011-9554-x","volume":"64","author":"M Lampis","year":"2012","unstructured":"Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19\u201337 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"20_CR27","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"FR McMorris","year":"1994","unstructured":"McMorris, F.R., Warnow, T.J., Wimer, T.: Triangulating vertex-colored graphs. SIAM J. Discrete Math. 7(2), 296\u2013306 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"959","DOI":"10.1016\/j.dam.2011.09.001","volume":"160","author":"K Meeks","year":"2012","unstructured":"Meeks, K., Scott, A.: The complexity of flood-filling games on graphs. Discrete Appl. Math. 160, 959\u2013969 (2012)","journal-title":"Discrete Appl. Math."},{"key":"20_CR29","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tcs.2013.06.010","volume":"500","author":"K Meeks","year":"2013","unstructured":"Meeks, K., Scott, A.: The complexity of free-flood-it on $$2 \\times n$$ boards. Theor. Comput. Sci. 500, 25\u201343 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"20_CR30","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s00224-013-9482-z","volume":"54","author":"K Meeks","year":"2014","unstructured":"Meeks, K., Scott, A.: Spanning trees and the complexity of flood-filling games. Theory Comput. Syst. 54(4), 731\u2013753 (2014)","journal-title":"Theory Comput. Syst."},{"key":"20_CR31","unstructured":"Meeks, K., Vu, D.K.: Extremal properties of flood-filling games. arXiv preprint arXiv:1504.00596 (2015)"},{"key":"20_CR32","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)00074-2","volume":"125","author":"M Middendorf","year":"1994","unstructured":"Middendorf, M.: More on the complexity of common superstring and supersequence problems. Theor. Comput. Sci. 125, 205\u2013228 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/11534273_20","volume-title":"Algorithms and Data Structures","author":"S Moran","year":"2005","unstructured":"Moran, S., Snir, S.: Convex recolorings of strings and trees: definitions, hardness results and algorithms. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, pp. 218\u2013232. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11534273_20"},{"key":"20_CR34","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14, 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"20_CR35","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2012.05.032","volume":"452","author":"GJ Woeginger","year":"2012","unstructured":"Woeginger, G.J., Fleischer, R.: An algorithmic analysis of the honey-bee game. Theor. Comput. Sci. 452, 75\u201387 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"Suppl. 2","key":"20_CR36","doi-asserted-by":"crossref","first-page":"ii156","DOI":"10.1093\/bioinformatics\/btg1073","volume":"19","author":"S Rahmann","year":"2003","unstructured":"Rahmann, S.: The shortest common supersequence problem in a microarray production setting. Bioinformatics 19(Suppl. 2), ii156\u2013ii161 (2003)","journal-title":"Bioinformatics"},{"key":"20_CR37","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K-J Raiha","year":"1981","unstructured":"Raiha, 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":"1","key":"20_CR38","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S1570-8667(03)00011-X","volume":"1","author":"J Sim","year":"2003","unstructured":"Sim, J., Park, K.: The consensus string problem for a metric is NP-complete. J. Discrete Algorithms 1(1), 111\u2013117 (2003)","journal-title":"J. Discrete Algorithms"},{"key":"20_CR39","unstructured":"Souza, U.S., Protti, F., Dantas da Silva, M.: Inunda\u00e7\u00e3o em grafos. In: Proceedings of the 16th Congreso Latino Iberoamericano de Investigaci\u00f3n Operativa & 44th Simp\u00f3sio Brasileiro de Pesquisa Operacional, CLAIO\/SBPO 2012 (2012)"},{"key":"20_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/978-3-642-38768-5_47","volume-title":"Computing and Combinatorics","author":"U dos Santos Souza","year":"2013","unstructured":"dos Santos Souza, U., Protti, F., da Silva, M.D.: Parameterized complexity of flood-filling games on trees. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 531\u2013542. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38768-5_47"},{"issue":"3","key":"20_CR41","first-page":"279","volume":"16","author":"U dos Santos Souza","year":"2014","unstructured":"dos Santos Souza, U., Protti, F., Silva, M.: An algorithmic analysis of flood-it and free-flood-it on graph powers. Discrete Math. Theor. Comput. Sci. 16(3), 279 (2014)","journal-title":"Discrete Math. Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T13:18:12Z","timestamp":1710335892000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}