{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:16:33Z","timestamp":1768706193431,"version":"3.49.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,4,20]],"date-time":"2017-04-20T00:00:00Z","timestamp":1492646400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00453-017-0311-7","type":"journal-article","created":{"date-parts":[[2017,4,20]],"date-time":"2017-04-20T09:59:15Z","timestamp":1492682355000},"page":"1857-1889","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth"],"prefix":"10.1007","volume":"80","author":[{"given":"Jessica","family":"Enright","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5299-3073","authenticated-orcid":false,"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,20]]},"reference":[{"key":"311_CR1","first-page":"417","volume":"3","author":"R Anderson","year":"1990","unstructured":"Anderson, R., Gupta, S., Ng, W.: The significance of sexual partner contact networks for the transmission dynamics of HIV. J. Acquir. Immune Defic. Syndr. Hum. Retrovirol. 3, 417\u2013429 (1990)","journal-title":"J. Acquir. Immune Defic. Syndr. Hum. Retrovirol."},{"key":"311_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -tree. SIAM J. Alg. Disc. Methods 8, 277\u2013284 (1987)","journal-title":"SIAM J. Alg. Disc. Methods"},{"key":"311_CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Sesse, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"311_CR4","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC \u201993, pp. 226\u2013234. ACM, New York (1993). doi:\n                        10.1145\/167088.167161","DOI":"10.1145\/167088.167161"},{"issue":"4","key":"311_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58(4), 171\u2013176 (1996). doi:\n                        10.1016\/0020-0190(96)00050-6","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"311_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109(12), 49\u201382 (1993). doi:\n                        10.1016\/0304-3975(93)90064-Z","journal-title":"Theor. Comput. Sci."},{"key":"311_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-319-13075-023","volume-title":"Algorithms and Computation","author":"PG Drange","year":"2014","unstructured":"Drange, P.G., Dregi, M.S., van \u2019t Hof, P.: On the computational complexity of vertex integrity and component order connectivity. In: Ahn, H.K., Shin, C.S. (eds.) Algorithms and Computation. Lecture Notes in Computer Science, pp. 285\u2013297. Springer International Publishing, Berlin (2014). doi:\n                        10.1007\/978-3-319-13075-023"},{"key":"311_CR8","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/31.1748","volume":"3","author":"ES El-Mallah","year":"1988","unstructured":"El-Mallah, E.S., Colbourn, C.J.: The complexity of some edge deletion problems. IEEE Trans. Circuits Syst. 3, 354\u2013362 (1988)","journal-title":"IEEE Trans. Circuits Syst."},{"issue":"45","key":"311_CR9","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1016\/j.dam.2011.10.013","volume":"160","author":"Y Gao","year":"2012","unstructured":"Gao, Y.: Treewidth of Erd\u0151s\u2013Renyi random graphs, random intersection graphs, and scale-free random graphs. Discret. Appl. Math. 160(45), 566\u2013578 (2012). doi:\n                        10.1016\/j.dam.2011.10.013","journal-title":"Discret. Appl. Math."},{"key":"311_CR10","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 & Co., New York (1979)"},{"key":"311_CR11","unstructured":"Gecode Team: Gecode: Generic constraint development environment (2016). \n                        http:\/\/www.gecode.org"},{"key":"311_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-642-31155-010","volume-title":"Algorithm Theory SWAT 2012","author":"E Ghosh","year":"2012","unstructured":"Ghosh, E., Kolay, S., Kumar, M., Misra, P., Panolan, F., Rai, A., Ramanujan, M.: Faster parameterized algorithms for deletion to split graphs. In: Fomin, F., Kaski, P. (eds.) Algorithm Theory SWAT 2012. Lecture Notes in Computer Science, pp. 107\u2013118. Springer, Berlin (2012). doi:\n                        10.1007\/978-3-642-31155-010"},{"key":"311_CR13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"PW Goldberg","year":"1993","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2, 139\u2013152 (1993)","journal-title":"J. Comput. Biol."},{"key":"311_CR14","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, vol. 57. Elsevier, Amsterdam (2004)"},{"issue":"9","key":"311_CR15","first-page":"895","volume":"12","author":"D Gross","year":"2013","unstructured":"Gross, D., Heinig, M., Iswara, L., Kazmierczak, L.W., Luttrell, K., Saccoman, J.T., Suffel, C.: A survey of component order connectivity models of graph theoretic networks. SWEAS Trans. Math. 12(9), 895\u2013910 (2013)","journal-title":"SWEAS Trans. Math."},{"key":"311_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1007\/978-3-540-77120-379","volume-title":"Algorithms and Computation","author":"J Guo","year":"2007","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Tokuyama, T. (ed.) Algorithms and Computation. Lecture Notes in Computer Science, vol. 4835, pp. 915\u2013926. Springer, Berlin (2007). doi:\n                        10.1007\/978-3-540-77120-379"},{"issue":"16","key":"311_CR17","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1098\/rsif.2007.1129","volume":"4","author":"RR Kao","year":"2007","unstructured":"Kao, R.R., Green, D.M., Johnson, J., Kiss, I.Z.: Disease dynamics over very different time-scales: foot-and-mouth disease and scrapie on the network of livestock movements in the UK. J. R. Soc. Interface 4(16), 907\u2013916 (2007). doi:\n                        10.1098\/rsif.2007.1129","journal-title":"J. R. Soc. Interface"},{"key":"311_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T., Treewidth, T.: Computations and Approximations. Lecture Notes in Computer Science. Springer, Berlin (1994). doi:\n                        10.1007\/BFb0045375"},{"issue":"2","key":"311_CR19","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980). doi:\n                        10.1016\/0022-0000(80)90060-4","journal-title":"J. Comput. Syst. Sci."},{"key":"311_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-642-20877-5_30","volume-title":"Theory and Applications of Models of Computation","author":"A Li","year":"2011","unstructured":"Li, A., Tang, L.: The complexity and approximability of minimum contamination problems. In: Ogihara, M., Tarui, J. (eds.) Theory and Applications of Models of Computation. Lecture Notes in Computer Science, vol. 6648, pp. 298\u2013307. Springer, Berlin (2011). doi:\n                        10.1007\/978-3-642-20877-5_30"},{"issue":"1:3","key":"311_CR21","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0166-218X(94)90214-3","volume":"49","author":"F Margot","year":"1994","unstructured":"Margot, F.: Some complexity results about threshold graphs. Discret. Appl. Math. 49(1:3), 299\u2013308 (1994). doi:\n                        10.1016\/0166-218X(94)90214-3","journal-title":"Discret. Appl. Math."},{"key":"311_CR22","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1079\/ASC50020265","volume":"80","author":"A Mitchell","year":"2005","unstructured":"Mitchell, A., Bourn, D., Mawdsley, J., Wint, W., Clifton-Hadley, R., Gilbert, M.: Characteristics of cattle movements in britain: an analysis of records from the cattle tracing system. Anim. Sci. 80, 265\u2013273 (2005). doi:\n                        10.1079\/ASC50020265","journal-title":"Anim. Sci."},{"issue":"1","key":"311_CR23","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discret. Appl. Math. 113(1), 109\u2013128 (2001). doi:\n                        10.1016\/S0166-218X(00)00391-7","journal-title":"Discret. Appl. Math."},{"key":"311_CR24","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming. CP\u201907, pp. 529\u2013543. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"311_CR25","unstructured":"Prud\u2019homme, C., Fages, J-G., Lorca, X.: Choco documentation (2016). \n                        http:\/\/www.choco-solver.org"},{"key":"311_CR26","doi-asserted-by":"publisher","unstructured":"Robertson, N., Seymour, P.: Graph minors. III. planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984). doi:\n                        10.1016\/0095-8956(84)90013-3\n                        \n                    . \n                        http:\/\/www.sciencedirect.com\/science\/article\/pii\/0095895684900133","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"311_CR27","unstructured":"Schulte, C., Tack, G., Lagerkvist, M.Z.: Modeling and programming with Gecode (2013). \n                        http:\/\/www.gecode.org"},{"issue":"2","key":"311_CR28","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1609\/aimag.v35i2.2539","volume":"35","author":"PJ Stuckey","year":"2014","unstructured":"Stuckey, P.J., Feydy, T., Schutt, A., Tack, G., Fischer, J.: The minizinc challenge 2008\u20132013. AI Mag. 35(2), 55\u201360 (2014)","journal-title":"AI Mag."},{"key":"311_CR29","unstructured":"van Dijk, T., van\u00a0den Heuvel, J.P., Slob, W.: Computing treewidth with LibTW (2006)"},{"issue":"1","key":"311_CR30","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0166-218X(83)90101-4","volume":"6","author":"T Watanabe","year":"1983","unstructured":"Watanabe, T., Ae, T., Nakamura, A.: On the NP-hardness of edge-deletion and -contraction problems. Discret. Appl. Math. 6(1), 63\u201378 (1983). doi:\n                        10.1016\/0166-218X(83)90101-4","journal-title":"Discret. Appl. Math."},{"key":"311_CR31","doi-asserted-by":"publisher","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC \u201978, pp. 253\u2013264. ACM, New York (1978). doi:\n                        10.1145\/800133.804355","DOI":"10.1145\/800133.804355"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0311-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0311-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0311-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,4,2]],"date-time":"2018-04-02T14:22:17Z","timestamp":1522678937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0311-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,20]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["311"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0311-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,4,20]]}}}