{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:38:19Z","timestamp":1742956699142,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_15","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"172-183","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Firefighter Problem: A Structural Analysis"],"prefix":"10.1007","author":[{"given":"Janka","family":"Chleb\u00edkov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morgan","family":"Chopin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"issue":"1\u20132","key":"15_CR1","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/s00453-010-9469-y","volume":"62","author":"E Anshelevich","year":"2012","unstructured":"Anshelevich, E., Chakrabarty, D., Hate, A., Swamy, C.: Approximability of the firefighter problem. Algorithmica 62(1\u20132), 520\u2013536 (2012)","journal-title":"Algorithmica"},{"issue":"7","key":"15_CR2","doi-asserted-by":"publisher","first-page":"1285","DOI":"10.1016\/j.jcss.2014.03.001","volume":"80","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Cygan, M., Fellows, M.R., Fomin, F.V., van Leeuwen, E.J.: Parameterized complexity of firefighting. J. Comput. Syst. Sci. 80(7), 1285\u20131297 (2014)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7\u20138","key":"15_CR3","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1016\/j.dam.2012.11.011","volume":"161","author":"C Bazgan","year":"2013","unstructured":"Bazgan, C., Chopin, M., Ries, B.: The firefighter problem with more than one firefighter on trees. Discrete Appl. Math. 161(7\u20138), 899\u2013908 (2013)","journal-title":"Discrete Appl. Math."},{"key":"15_CR4","first-page":"116","volume":"36","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Classes of graphs with bounded tree-width. Bull. EATCS 36, 116\u2013128 (1988)","journal-title":"Bull. EATCS"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-540-92182-0_25","volume-title":"Algorithms and Computation","author":"L Cai","year":"2008","unstructured":"Cai, L., Verbin, E., Yang, L.: Firefighting on trees: (1 $$-$$ 1\/e)\u2013approximation, fixed parameter tractability and a subexponential algorithm. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 258\u2013269. Springer, Heidelberg (2008)"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Chung, F.R., Seymour, P.D.: Graphs with small bandwidth and cutwidth. In: Graph Theory and combinatorics 1988 Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erd\u00f6s, Annals of Discrete Mathematics, vol. 43, pp. 113\u2013119 (1989)","DOI":"10.1016\/S0167-5060(08)70571-5"},{"issue":"16\u201317","key":"15_CR7","doi-asserted-by":"publisher","first-page":"2410","DOI":"10.1016\/j.dam.2013.04.008","volume":"161","author":"V Costa","year":"2013","unstructured":"Costa, V., Dantas, S., Dourado, M.C., Penso, L., Rautenbach, D.: More fires and more fighters. Discrete Appl. Math. 161(16\u201317), 2410\u20132419 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"17","key":"15_CR8","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1016\/j.dam.2007.06.002","volume":"155","author":"M Develin","year":"2007","unstructured":"Develin, M., Hartke, S.G.: Fire containment in grids of dimension three and higher. Discrete Appl. Math. 155(17), 2257\u20132268 (2007)","journal-title":"Discrete Appl. Math."},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-642-32589-2_32","volume-title":"Mathematical Foundations of Computer Science 2012","author":"M Doucha","year":"2012","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 348\u2013359. Springer, Heidelberg (2012)"},{"issue":"16","key":"15_CR10","doi-asserted-by":"publisher","first-page":"2094","DOI":"10.1016\/j.disc.2005.12.053","volume":"307","author":"S Finbow","year":"2007","unstructured":"Finbow, S., King, A., MacGillivray, G., Rizzi, R.: The firefighter problem for graphs of maximum degree three. Discrete Math. 307(16), 2094\u20132105 (2007)","journal-title":"Discrete Math."},{"key":"15_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-30347-0_19","volume-title":"Fun with Algorithms","author":"FV Fomin","year":"2012","unstructured":"Fomin, F.V., Heggernes, P., van Leeuwen, E.J.: Making Life Easier for Firefighters. In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol. 7288, pp. 177\u2013188. Springer, Heidelberg (2012)"},{"key":"15_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H Freeman and Company, New York (1979)"},{"key":"15_CR13","unstructured":"Hartnell, B.: Firefighter! an application of domination, Presentation. In: 10th Conference on Numerical Mathematics and Computing, University of Manitoba in Winnipeg, Canada (1995)"},{"key":"15_CR14","first-page":"187","volume":"145","author":"B Hartnell","year":"2000","unstructured":"Hartnell, B., Li, Q.: Firefighting on trees: how bad is the greedy algorithm? Congressus Numerantium 145, 187\u2013192 (2000)","journal-title":"Congressus Numerantium"},{"issue":"2","key":"15_CR15","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1587\/transinf.E94.D.196","volume":"E94.D","author":"Y Iwaikawa","year":"2011","unstructured":"Iwaikawa, Y., Kamiyama, N., Matsui, T.: Improved approximation algorithms for firefighter problem on trees. IEICE Trans. Inf. Syst. E94.D(2), 196\u2013199 (2011)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"3","key":"15_CR16","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/j.disc.2009.05.007","volume":"310","author":"A King","year":"2010","unstructured":"King, A., MacGillivray, G.: The firefighter problem for cubic graphs. Discrete Math. 310(3), 614\u2013621 (2010)","journal-title":"Discrete Math."},{"issue":"1","key":"15_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(93)90171-J","volume":"43","author":"E Korach","year":"1993","unstructured":"Korach, E., Solel, N.: Tree-width, path-width, and cutwidth. Discrete Appl. Math. 43(1), 97\u2013101 (1993)","journal-title":"Discrete Appl. Math."},{"key":"15_CR18","first-page":"83","volume":"47","author":"G MacGillivray","year":"2003","unstructured":"MacGillivray, G., Wang, P.: On the firefighter problem. J. Comb. Math. Comb. Comput. 47, 83\u201396 (2003)","journal-title":"J. Comb. Math. Comb. Comput."},{"issue":"5","key":"15_CR19","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1016\/j.dam.2007.08.011","volume":"156","author":"KL Ng","year":"2008","unstructured":"Ng, K.L., Raff, P.: A generalization of the firefighter problem on ZxZ. Discrete Appl. Math. 156(5), 730\u2013745 (2008)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T12:22:05Z","timestamp":1675254125000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}