{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T03:10:42Z","timestamp":1778037042801,"version":"3.51.4"},"reference-count":57,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T00:00:00Z","timestamp":1754006400000},"content-version":"vor","delay-in-days":1461,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T00:00:00Z","timestamp":1627776000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1016\/j.jcss.2021.01.007","type":"journal-article","created":{"date-parts":[[2021,2,15]],"date-time":"2021-02-15T00:32:20Z","timestamp":1613349140000},"page":"60-77","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":41,"special_numbering":"C","title":["Deleting edges to restrict the size of an epidemic in temporal networks"],"prefix":"10.1016","volume":"119","author":[{"given":"Jessica","family":"Enright","sequence":"first","affiliation":[]},{"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7182-585X","authenticated-orcid":false,"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[]},{"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jcss.2021.01.007_br0010","series-title":"Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","first-page":"29","article-title":"DMVP: foremost waypoint coverage of time-varying graphs","volume":"vol. 8747","author":"Aaron","year":"2014"},{"key":"10.1016\/j.jcss.2021.01.007_br0020","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.jpdc.2015.10.002","article-title":"Ephemeral networks with random availability of links: the case of fast networks","volume":"87","author":"Akrida","year":"2016","journal-title":"J. Parallel Distrib. Comput."},{"issue":"3","key":"10.1016\/j.jcss.2021.01.007_br0030","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1007\/s00224-017-9757-x","article-title":"The complexity of optimal design of temporally connected graphs","volume":"61","author":"Akrida","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.jcss.2021.01.007_br0040","series-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","article-title":"How fast can we reach a target vertex in stochastic temporal graphs?","volume":"vol. 132","author":"Akrida","year":"2019"},{"key":"10.1016\/j.jcss.2021.01.007_br0050","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","article-title":"Temporal vertex cover with a sliding time window","volume":"107","author":"Akrida","year":"2020","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1016\/j.jcss.2021.01.007_br0060","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/j.jcss.2021.01.007_br0070","series-title":"Dynamical Processes on Complex Networks","author":"Barrat","year":"2008"},{"key":"10.1016\/j.jcss.2021.01.007_br0080","series-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","first-page":"226","article-title":"A linear-time algorithm for finding tree-decompositions of small treewidth","author":"Bodlaender","year":"1993"},{"key":"10.1016\/j.jcss.2021.01.007_br0090","doi-asserted-by":"crossref","DOI":"10.1038\/srep27538","article-title":"Inference of causality in epidemics on temporal contact networks","volume":"6","author":"Braunstein","year":"2016","journal-title":"Sci. Rep."},{"issue":"6164","key":"10.1016\/j.jcss.2021.01.007_br0100","doi-asserted-by":"crossref","first-page":"1337","DOI":"10.1126\/science.1245200","article-title":"The hidden geometry of complex, network-driven contagion phenomena","volume":"342","author":"Brockmann","year":"2013","journal-title":"Science"},{"issue":"2","key":"10.1016\/j.jcss.2021.01.007_br0110","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0129054103001728","article-title":"Computing shortest, fastest, and foremost journeys in dynamic networks","volume":"14","author":"Bui-Xuan","year":"2003","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10.1016\/j.jcss.2021.01.007_br0120","series-title":"Deterministic Algorithms in Dynamic Networks: Formal Models and Metrics","author":"Casteigts","year":"2013"},{"key":"10.1016\/j.jcss.2021.01.007_br0130","series-title":"Deterministic Algorithms in Dynamic Networks: Problems, Analysis, and Algorithmic Tools","author":"Casteigts","year":"2013"},{"issue":"5","key":"10.1016\/j.jcss.2021.01.007_br0140","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1080\/17445760.2012.668546","article-title":"Time-varying graphs and dynamic networks","volume":"27","author":"Casteigts","year":"2012","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"10.1016\/j.jcss.2021.01.007_br0150","author":"Casteigts"},{"issue":"2","key":"10.1016\/j.jcss.2021.01.007_br0160","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","article-title":"Tight lower bounds for certain parameterized NP-hard problems","volume":"201","author":"Chen","year":"2005","journal-title":"Inf. Comput."},{"issue":"4","key":"10.1016\/j.jcss.2021.01.007_br0170","doi-asserted-by":"crossref","first-page":"1694","DOI":"10.1137\/090756053","article-title":"Flooding time of edge-Markovian evolving graphs","volume":"24","author":"Clementi","year":"2010","journal-title":"SIAM J. Discrete Math."},{"issue":"7","key":"10.1016\/j.jcss.2021.01.007_br0180","doi-asserted-by":"crossref","first-page":"2015","DOI":"10.1073\/pnas.0510525103","article-title":"The role of the airline transportation network in the prediction and predictability of global epidemics","volume":"103","author":"Colizza","year":"2006","journal-title":"Proc. Natl. Acad. Sci."},{"key":"10.1016\/j.jcss.2021.01.007_br0190","series-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"Courcelle","year":"2012"},{"key":"10.1016\/j.jcss.2021.01.007_br0200","series-title":"Proceedings of the 46th Annual ACM Symposium on Theory of Computing","first-page":"624","article-title":"Analytical approach to parallel repetition","author":"Dinur","year":"2014"},{"issue":"6","key":"10.1016\/j.jcss.2021.01.007_br0210","doi-asserted-by":"crossref","first-page":"1857","DOI":"10.1007\/s00453-017-0311-7","article-title":"Deleting edges to restrict the size of an epidemic: a new application for treewidth","volume":"80","author":"Enright","year":"2018","journal-title":"Algorithmica"},{"key":"10.1016\/j.jcss.2021.01.007_br0220","series-title":"Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science","article-title":"Deleting edges to restrict the size of an epidemic in temporal networks","volume":"vol. 138","author":"Enright","year":"2019"},{"key":"10.1016\/j.jcss.2021.01.007_br0230","author":"Enright"},{"key":"10.1016\/j.jcss.2021.01.007_br0240","series-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming","first-page":"444","article-title":"On temporal graph exploration","volume":"vol. 9134","author":"Erlebach","year":"2015"},{"issue":"5","key":"10.1016\/j.jcss.2021.01.007_br0250","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/MNET.2004.1337732","article-title":"Building a reference combinatorial model for MANETs","volume":"18","author":"Ferreira","year":"2004","journal-title":"IEEE Netw."},{"key":"10.1016\/j.jcss.2021.01.007_br0260","first-page":"57","article-title":"The firefighter problem: a survey of results, directions and questions","volume":"43","author":"Finbow","year":"2009","journal-title":"Australas. J. Comb."},{"key":"10.1016\/j.jcss.2021.01.007_br0270","series-title":"Proceedings of the 20th International Symposium on Algorithms and Computation","first-page":"534","article-title":"Exploration of periodically varying graphs","volume":"vol. 5878","author":"Flocchini","year":"2009"},{"key":"10.1016\/j.jcss.2021.01.007_br0280","series-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"key":"10.1016\/j.jcss.2021.01.007_br0290","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.tcs.2019.03.031","article-title":"Temporal graph classes: a view through temporal separators","volume":"806","author":"Fluschnik","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2021.01.007_br0300","series-title":"Proceedings of the 41st International Colloquium on Automata, Languages and Programming","first-page":"495","article-title":"Randomized rumor spreading in dynamic graphs","volume":"vol. 8573","author":"Giakkoupis","year":"2014"},{"issue":"8","key":"10.1016\/j.jcss.2021.01.007_br0310","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1038\/nrmicro960","article-title":"The UK foot-and-mouth disease outbreak\u2014the aftermath","volume":"2","author":"Haydon","year":"2004","journal-title":"Nat. Rev. Microbiol."},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0320","doi-asserted-by":"crossref","DOI":"10.1177\/2056305117691545","article-title":"Classifying Twitter topic-networks using social network analysis","volume":"3","author":"Himelboim","year":"2017","journal-title":"Social Media + Society"},{"key":"10.1016\/j.jcss.2021.01.007_br0330","series-title":"Complex Networks and Their Applications VIII","first-page":"494","article-title":"Efficient computation of optimal temporal walks under waiting-time constraints","author":"Himmel","year":"2020"},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0340","doi-asserted-by":"crossref","DOI":"10.1007\/s13278-017-0455-0","article-title":"Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs","volume":"7","author":"Himmel","year":"2017","journal-title":"Soc. Netw. Anal. Min."},{"key":"10.1016\/j.jcss.2021.01.007_br0350","series-title":"Temporal Networks","year":"2013"},{"key":"10.1016\/j.jcss.2021.01.007_br0360","series-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing","first-page":"504","article-title":"Connectivity and inference problems for temporal networks","author":"Kempe","year":"2000"},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0370","doi-asserted-by":"crossref","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: densification and shrinking diameters","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"10.1016\/j.jcss.2021.01.007_br0380","author":"Leskovec"},{"key":"10.1016\/j.jcss.2021.01.007_br0390","series-title":"Proceedings of the 40th International Colloquium on Automata, Languages and Programming","first-page":"657","article-title":"Temporal network optimization subject to connectivity constraints","volume":"vol. 7966","author":"Mertzios","year":"2013"},{"key":"10.1016\/j.jcss.2021.01.007_br0400","series-title":"Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science","article-title":"Computing maximum matchings in temporal graphs","volume":"vol. 154","author":"Mertzios","year":"2020"},{"key":"10.1016\/j.jcss.2021.01.007_br0410","series-title":"Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33","first-page":"7667","article-title":"Sliding window temporal graph coloring","author":"Mertzios","year":"2019"},{"key":"10.1016\/j.jcss.2021.01.007_br0420","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","article-title":"Traveling salesman problems in temporal graphs","volume":"634","author":"Michail","year":"2016","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10.1016\/j.jcss.2021.01.007_br0430","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1145\/3156693","article-title":"Elements of the theory of dynamic networks","volume":"61","author":"Michail","year":"2018","journal-title":"Commun. ACM"},{"issue":"3","key":"10.1016\/j.jcss.2021.01.007_br0440","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1079\/ASC50020265","article-title":"Characteristics of cattle movements in Britain \u2013 an analysis of records from the cattle tracing system","volume":"80","author":"Mitchell","year":"2005","journal-title":"Anim. Sci."},{"issue":"3","key":"10.1016\/j.jcss.2021.01.007_br0450","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1079\/ASC50020265","article-title":"Characteristics of cattle movements in Britain \u2013 an analysis of records from the cattle tracing system","volume":"80","author":"Mitchell","year":"2005","journal-title":"Anim. Sci."},{"key":"10.1016\/j.jcss.2021.01.007_br0460","series-title":"Proceedings of the 15th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","first-page":"276","article-title":"The projection games conjecture and the NP-hardness of ln n-approximating set-cover","author":"Moshkovitz","year":"2012"},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0470","doi-asserted-by":"crossref","DOI":"10.1186\/1746-6148-10-71","article-title":"EpiContactTrace: an R-package for contact tracing during livestock disease outbreaks and for risk-based surveillance","volume":"10","author":"Noremark","year":"2014","journal-title":"BMC Vet. Res."},{"issue":"7","key":"10.1016\/j.jcss.2021.01.007_br0480","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pone.0130824","article-title":"Tracking human mobility using WiFi signals","volume":"10","author":"Sapiezynski","year":"2015","journal-title":"PLoS ONE"},{"key":"10.1016\/j.jcss.2021.01.007_br0490","series-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver","year":"2003"},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0500","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/1672308.1672329","article-title":"Characterising temporal distance and reachability in mobile and online social networks","volume":"40","author":"Tang","year":"2010","journal-title":"Comput. Commun. Rev."},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0510","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","article-title":"Cutwidth I: a linear time fixed parameter algorithm","volume":"56","author":"Thilikos","year":"2005","journal-title":"J. Algorithms"},{"issue":"1","key":"10.1016\/j.jcss.2021.01.007_br0520","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","article-title":"A simplified NP-complete satisfiability problem","volume":"8","author":"Tovey","year":"1984","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.jcss.2021.01.007_br0530","article-title":"Analytical computation of the epidemic threshold on temporal networks","volume":"5","author":"Valdano","year":"2015","journal-title":"Phys. Rev. X"},{"issue":"3","key":"10.1016\/j.jcss.2021.01.007_br0540","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pcbi.1004152","article-title":"Predicting epidemic risk from past temporal contact data","volume":"11","author":"Valdano","year":"2015","journal-title":"PLoS Comput. Biol."},{"key":"10.1016\/j.jcss.2021.01.007_br0550","series-title":"Proceedings of the 2015 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining","first-page":"1517","article-title":"Revealing contact patterns among high-school students using maximal cliques in link streams","author":"Viard","year":"2015"},{"key":"10.1016\/j.jcss.2021.01.007_br0560","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.tcs.2015.09.030","article-title":"Computing maximal cliques in link streams","volume":"609","author":"Viard","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2021.01.007_br0570","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.jcss.2019.07.006","article-title":"The complexity of finding small separators in temporal graphs","volume":"107","author":"Zschoche","year":"2020","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000021000155?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000021000155?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,8,1]],"date-time":"2025-08-01T01:34:46Z","timestamp":1754012086000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000021000155"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8]]},"references-count":57,"alternative-id":["S0022000021000155"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2021.01.007","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2021,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Deleting edges to restrict the size of an epidemic in temporal networks","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2021.01.007","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2021 Elsevier Inc.","name":"copyright","label":"Copyright"}]}}