{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:43:30Z","timestamp":1725453810833},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_47","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T00:31:28Z","timestamp":1368750688000},"page":"531-542","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Complexity of Flood-Filling Games on Trees"],"prefix":"10.1007","author":[{"given":"U\u00e9verton","family":"dos Santos Souza","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F\u00e1bio","family":"Protti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maise Dantas","family":"da Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"47_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.\u00a06099, pp. 307\u2013318. Springer, Heidelberg (2010)"},{"key":"47_CR2","volume-title":"Proceedings of the 37th Annual Hawaii International Conference on System Sciences","author":"C. Aschwanden","year":"2004","unstructured":"Aschwanden, C.: Spatial Simulation Model for Infectious Viral Disease with Focus on SARS and the Common Flu. In: Proceedings of the 37th Annual Hawaii International Conference on System Sciences. IEEE Computer Society, Washington, DC (2004)"},{"key":"47_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":"47_CR4","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(98)00342-9","volume":"244","author":"H.L. 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. Theoretical Computer Science\u00a0244, 167\u2013188 (2000)","journal-title":"Theoretical Computer Science"},{"key":"47_CR5","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.R., Ragan, M.A., Razgon, I., Rosamond, F.A., Snir, S.: Connected Coloring Completion for General Graphs: Algorithms and Complexity. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 75\u201385. Springer, Heidelberg (2007)"},{"issue":"1","key":"47_CR6","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 of Computing Systems\u00a050(1), 72\u201392 (2012)","journal-title":"Theory of Computing Systems"},{"key":"47_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4612-2566-9_7","volume-title":"Feasible Mathematics II","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Parametrized Computational Feasibility. In: Clote, P., Remmel, J. (eds.) Feasible Mathematics II, pp. 219\u2013244. Birkhauser, Boston (1995)"},{"key":"47_CR8","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":"M.R. 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.\u00a04596, pp. 340\u2013351. Springer, Heidelberg (2007)"},{"issue":"1","key":"47_CR9","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0196-6774(03)00081-6","volume":"49","author":"M.R. Fellows","year":"2003","unstructured":"Fellows, M.R., Hallett, M.T., Stege, U.: Analogs & Duals of the MAST problem for Sequences & Trees. Journal of Algorithms\u00a049(1), 192\u2013216 (2003)","journal-title":"Journal of Algorithms"},{"key":"47_CR10","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 - ESA \u201993","author":"M.R. 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.\u00a0726, pp. 157\u2013168. Springer, Heidelberg (1993)"},{"key":"47_CR11","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/367390.367400","volume":"3","author":"E. Fredkin","year":"1960","unstructured":"Fredkin, E.: Trie Memory. Communications of the ACM\u00a03, 490\u2013499 (1960)","journal-title":"Communications of the ACM"},{"key":"47_CR12","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. Advances in Applied Mathematics\u00a015, 251\u2013261 (1994)","journal-title":"Advances in Applied Mathematics"},{"key":"47_CR13","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 Trees. Networks\u00a021, 19\u201328 (1981)","journal-title":"Networks"},{"key":"47_CR14","unstructured":"Hallett, M.T.: An Integrated Complexity Analysis of Problems from Computational Biology. PhD thesis, University of Victoria (1996)"},{"issue":"4","key":"47_CR15","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 Transactions on Computational Biology and Bioinformatics\u00a03(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"47_CR16","unstructured":"Lagoutte, A., Noual, M., Thierry, E.: Flooding Games on Graphs, HAL: hal-00653714 (December 2011)"},{"issue":"2","key":"47_CR17","doi-asserted-by":"publisher","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. Journal of the ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"Journal of the ACM"},{"issue":"2","key":"47_CR18","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"F.R. McMorris","year":"1994","unstructured":"McMorris, F.R., Warnow, T.J., Wimer, T.: Triangulating Vertex-Colored Graphs. SIAM Journal on Discrete Mathematics\u00a07(2), 296\u2013306 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"47_CR19","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 Applied Mathematics\u00a0160, 959\u2013969 (2012)","journal-title":"Discrete Applied Mathematics"},{"key":"47_CR20","unstructured":"Meeks, K., Scott, A.: The Complexity of Free-Flood-It on 2 \u00d7n Boards, arXiv:1101.5518v1 [cs.DS] (January 2011)"},{"key":"47_CR21","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.\u00a03608, pp. 218\u2013232. Springer, Heidelberg (2005)"},{"issue":"4","key":"47_CR22","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the Parameterized Complexity of the Fixed Alphabet Shortest Common Supersequence and Longest Common Subsequence Problems. Journal of Computer and System Sciences\u00a067(4), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"47_CR23","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"},{"issue":"1","key":"47_CR24","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. Journal of Discrete Algorithms\u00a01(1), 111\u2013117 (2003)","journal-title":"Journal of Discrete Algorithms"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T16:10:51Z","timestamp":1688227851000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}