{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T20:36:06Z","timestamp":1774730166756,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,12,22]],"date-time":"2010-12-22T00:00:00Z","timestamp":1292976000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9469-y","type":"journal-article","created":{"date-parts":[[2010,12,21]],"date-time":"2010-12-21T19:25:45Z","timestamp":1292959545000},"page":"520-536","source":"Crossref","is-referenced-by-count":27,"title":["Approximability of the Firefighter Problem"],"prefix":"10.1007","volume":"62","author":[{"given":"Elliot","family":"Anshelevich","sequence":"first","affiliation":[]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[]},{"given":"Ameya","family":"Hate","sequence":"additional","affiliation":[]},{"given":"Chaitanya","family":"Swamy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,12,22]]},"reference":[{"key":"9469_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R. Ahuja","year":"1993","unstructured":"Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New York (1993)"},{"issue":"6","key":"9469_CR2","doi-asserted-by":"crossref","first-page":"1077","DOI":"10.1016\/j.jcss.2006.02.003","volume":"72","author":"J. Aspnes","year":"2006","unstructured":"Aspnes, J., Chang, K., Yamposlkiy, A.: Inoculation strategies for victims of viruses and the sum-of-squares partition problem. J. Comput. Syst. Sci. 72(6), 1077\u20131093 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9469_CR3","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/11786986_59","volume":"4051","author":"G. Baier","year":"2006","unstructured":"Baier, G., Erlebach, T., Hall, A., K\u00f6hler, E., Schilling, H., Skutella, M.: Length-bounded cuts and flows. Autom. Lang. Program. 4051, 679\u2013690 (2006)","journal-title":"Autom. Lang. Program."},{"key":"9469_CR4","volume-title":"The Mathematical Theory of Infectious Diseases and its Applications","author":"N. Bailey","year":"1975","unstructured":"Bailey, N.: The Mathematical Theory of Infectious Diseases and its Applications. Hafner, New York (1975)"},{"key":"9469_CR5","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0378-4371(99)00291-5","volume":"272","author":"A. Barabasi","year":"1999","unstructured":"Barabasi, A., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Phys. A, Stat. Mech. Appl. 272, 173\u2013187 (1999)","journal-title":"Phys. A, Stat. Mech. Appl."},{"key":"9469_CR6","first-page":"301","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"N. Berger","year":"2005","unstructured":"Berger, N., Borgs, C., Chayes, J., Saberi, A.: On the spread of viruses on the internet. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 301\u2013310 (2005)"},{"key":"9469_CR7","volume-title":"Integer Programming and Combinatorial Optimization, 12th International IPCO Conference","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., Pal, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. In: Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA (2007)"},{"key":"9469_CR8","doi-asserted-by":"crossref","first-page":"1334","DOI":"10.1137\/1.9781611973075.108","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"P. Chalermsook","year":"2010","unstructured":"Chalermsook, P., Chuzhoy, J.: Resource minimization for fire containment. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1334\u20131349 (2010)"},{"key":"9469_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/978-3-540-27821-4_7","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"C. Chekuri","year":"2004","unstructured":"Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Approximation, Randomization, and Combinatorial Optimization. LNCS, pp. 72\u201383. Springer, Berlin (2004)"},{"issue":"17","key":"9469_CR10","doi-asserted-by":"crossref","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 or higher. Discrete Appl. Math. 155(17), 2257\u20132268 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9469_CR11","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.65.055103","volume":"65","author":"Z. Dezs\u0151","year":"2002","unstructured":"Dezs\u0151, Z., Barab\u00e1si, A.: Halting viruses in scale-free networks. Phys. Rev. E 65(5), 055103 (2002)","journal-title":"Phys. Rev. E"},{"issue":"7","key":"9469_CR12","doi-asserted-by":"crossref","first-page":"1615","DOI":"10.1016\/j.dam.2008.09.012","volume":"157","author":"P. Dreyer Jr.","year":"2009","unstructured":"Dreyer, P. Jr., Roberts, F.: Irreversible k-threshold processes: graph-theoretical threshold models of the spread of disease and of opinion. Discrete Appl. Math. 157(7), 1615\u20131627 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9469_CR13","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.jda.2006.05.002","volume":"5","author":"R. Engelberg","year":"2007","unstructured":"Engelberg, R., K\u00f6nemann, J., Leonardi, S., Naor, J.: Cut problems in graphs with a budget constraint. J. Discrete Algorithms 5(2), 262\u2013279 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"9469_CR14","first-page":"711","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"S. Eubank","year":"2004","unstructured":"Eubank, S., Kumar, V., Marathe, M., Srinivasan, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 711\u2013720 (2004)"},{"key":"9469_CR15","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln\u2009n for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"9469_CR16","doi-asserted-by":"crossref","first-page":"2094","DOI":"10.1016\/j.disc.2005.12.053","volume":"307","author":"S. Finbow","year":"2007","unstructured":"Finbow, S., King, A.D., MacGillivray, Gary, Rizzi, R.: The fire fighter problem on graphs of maximum degree three. Discrete Math. 307, 2094\u20132105 (2007)","journal-title":"Discrete Math."},{"key":"9469_CR17","unstructured":"Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and questions. Manuscript (2007)"},{"key":"9469_CR18","unstructured":"Fogarty, P.: Catching fire on grids. M.Sc. thesis, Department of Mathematics, University of Vermont (2003)"},{"key":"9469_CR19","first-page":"1455","volume-title":"Proc. 24th IEEE INFOCOM Conference","author":"A. Ganesh","year":"2005","unstructured":"Ganesh, A., Massoulie, L., Towlsey, D.: The effect of network topology on the spread of epidemics. In: Proc. 24th IEEE INFOCOM Conference, vol. 2, pp. 1455\u20131466 (2005)"},{"key":"9469_CR20","volume-title":"25th Manitoba Conference on Combinatorial Mathematics and Computing","author":"B. Hartnell","year":"1995","unstructured":"Hartnell, B.: Firefighter! An application of domination. Presentation. In: 25th Manitoba Conference on Combinatorial Mathematics and Computing, University of Manitoba in Winnipeg, Canada, (1995)"},{"key":"9469_CR21","first-page":"187","volume":"145","author":"B. Hartnell","year":"2000","unstructured":"Hartnell, B., Li, Q.: Firefighting on trees: how bad is the greedy algorithm? Congr. Numer. 145, 187\u2013192 (2000)","journal-title":"Congr. Numer."},{"key":"9469_CR22","volume-title":"Proceedings of European Symposium on Algorithms (ESA)","author":"A. Hayrapetyan","year":"2005","unstructured":"Hayrapetyan, A., Kempe, D., Pal, M., Svitkina, Z.: Unbalanced graph cuts. In: Proceedings of European Symposium on Algorithms (ESA) (2005)"},{"key":"9469_CR23","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)","author":"D. Kempe","year":"2005","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Influential nodes in a diffusion model for social networks. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP) (2005)"},{"key":"9469_CR24","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1109\/SFCS.2000.892065","volume-title":"Proc. 41st IEEE Symp. on Foundations of Computer Science (FOCS)","author":"R. Kumar","year":"2000","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: Proc. 41st IEEE Symp. on Foundations of Computer Science (FOCS), pp.\u00a057\u201365 (2000)"},{"key":"9469_CR25","first-page":"258","volume-title":"Proceedings of International Symposium on Algorithms and Computation 2008","author":"L. Cai","year":"2008","unstructured":"Cai, L., Verbin, E., Yang, L.: Firefighting on trees: (1\u22121\/e) approximation, fixed parameter tractability and a subexponential algorithm. In: Proceedings of International Symposium on Algorithms and Computation 2008, pp. 258\u2013269 (2008)"},{"key":"9469_CR26","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."},{"key":"9469_CR27","doi-asserted-by":"crossref","first-page":"5678","DOI":"10.1103\/PhysRevE.61.5678","volume":"61","author":"C. Moore","year":"2000","unstructured":"Moore, C., Newman, M.: Epidemics and percolation in small-world networks. Phys. Rev. E 61, 5678\u20135682 (2000)","journal-title":"Phys. Rev. E"},{"key":"9469_CR28","doi-asserted-by":"crossref","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"G. Nemhauser","year":"1988","unstructured":"Nemhauser, G., Wolsey, L.: Integer and Combinatorial Optimization. Wiley, New York (1988)"},{"key":"9469_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198504184.001.0001","volume-title":"Virus Dynamics: Mathematical Principles of Immunology and Virology","author":"M. Nowak","year":"2000","unstructured":"Nowak, M., May, R.: Virus Dynamics: Mathematical Principles of Immunology and Virology. Oxford University Press, Oxford (2000)"},{"key":"9469_CR30","volume":"65","author":"R. Pastor-Satorras","year":"2002","unstructured":"Pastor-Satorras, R., Vespignani, A.: Epidemic dynamics in finite scale-free networks. Phys. Rev. E 65, 035108(R) (2002)","journal-title":"Phys. Rev. E"},{"key":"9469_CR31","first-page":"19","volume":"41","author":"P. Wang","year":"2002","unstructured":"Wang, P., Moeller, S.: Fire control on graphs. J. Comb. Math. Comb. Comput. 41, 19\u201334 (2002)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"9469_CR32","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D. Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9469-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9469-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9469-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T05:47:40Z","timestamp":1712036860000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9469-y"}},"subtitle":["Computing Cuts over Time"],"short-title":[],"issued":{"date-parts":[[2010,12,22]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9469"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9469-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,22]]}}}