{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T04:46:33Z","timestamp":1768711593602,"version":"3.49.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031826696","type":"print"},{"value":"9783031826702","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-82670-2_19","type":"book-chapter","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T04:40:00Z","timestamp":1738816800000},"page":"255-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reachability in\u00a0Temporal Graphs Under Perturbation"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0266-3292","authenticated-orcid":false,"given":"Jessica","family":"Enright","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3322-0176","authenticated-orcid":false,"given":"Laura","family":"Larios-Jones","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5299-3073","authenticated-orcid":false,"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0040-2088","authenticated-orcid":false,"given":"William","family":"Pettersson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,7]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","unstructured":"Baswana, S., Choudhary, K., Roditty, L.: Fault tolerant subgraph for single source reachability: generic and optimal. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC \u201916, pp. 509\u2013518. Association for Computing Machinery, New York, NY, USA (2016). https:\/\/doi.org\/10.1145\/2897518.2897648","DOI":"10.1145\/2897518.2897648"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-031-22050-0_3","volume-title":"Algorithmics of Wireless Networks - ALGOSENSORS 2022","author":"D Bil\u00f3","year":"2022","unstructured":"Bil\u00f3, D., D\u2019Angelo, G., Gual\u00e1, L., Leucci, S., Rossi, M.: Blackout-tolerant temporal spanners. In: Erlebach, T., Segal, M. (eds.) ALGOSENSORS 2022. LNCS, vol. 13707, pp. 31\u201344. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-22050-0_3"},{"key":"19_CR3","unstructured":"Casteigts, A.: A journey through dynamic networks (with excursions). Thesis, Universit\u00e9 de Bordeaux (2018). https:\/\/hal.science\/tel-01883384"},{"key":"19_CR4","doi-asserted-by":"publisher","unstructured":"Casteigts, A., Dubois, S., Petit, F., Robson, J.M.: Robustness: a new form of heredity motivated by dynamic networks. Theor. Comput. Sci. 806, 429\u2013445 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2019.08.008, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397519304979","DOI":"10.1016\/j.tcs.2019.08.008"},{"key":"19_CR5","doi-asserted-by":"publisher","unstructured":"Chaters, G.L., et al.: Analysing livestock network data for infectious disease control: an argument for routine data collection in emerging economies. Philos. Trans. Roy. Soc. B: Biol. Sci. 374(1776), 20180264 (2019). Royal Society, https:\/\/doi.org\/10.1098\/rstb.2018.0264, https:\/\/royalsocietypublishing.org\/doi\/full\/10.1098\/rstb.2018.0264","DOI":"10.1098\/rstb.2018.0264"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Deligkas, A., D\u00f6ring, M., Eiben, E., Goldsmith, T.L., Skretas, G.: Being an influencer is hard: the complexity of influence maximization in temporal graphs with a fixed source (2023). arXiv:2303.11703 [cs]","DOI":"10.1016\/j.ic.2024.105171"},{"key":"19_CR7","doi-asserted-by":"publisher","unstructured":"Deligkas, A., Eiben, E., Skretas, G.: Minimizing reachability times on temporal graphs via shifting labels. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI \u201923, pp. 5333\u20135340 (2023). https:\/\/doi.org\/10.24963\/ijcai.2023\/592","DOI":"10.24963\/ijcai.2023\/592"},{"key":"19_CR8","doi-asserted-by":"publisher","unstructured":"Deligkas, A., Potapov, I.: Optimizing reachability sets in temporal graphs by delaying. Inf. Comput. 285, 104890 (2022). https:\/\/doi.org\/10.1016\/j.ic.2022.104890, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0890540122000323","DOI":"10.1016\/j.ic.2022.104890"},{"key":"19_CR9","doi-asserted-by":"publisher","unstructured":"Dinitz, M., Krauthgamer, R.: Fault-tolerant spanners: better and simpler. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC \u201911, pp. 169\u2013178. Association for Computing Machinery, New York, NY, USA (2011). https:\/\/doi.org\/10.1145\/1993806.1993830","DOI":"10.1145\/1993806.1993830"},{"key":"19_CR10","doi-asserted-by":"publisher","unstructured":"Dubois, S., Feuilloley, L., Petit, F., Rabie, M.: When should you wait before updating? - toward a robustness refinement. In: Doty, D., Spirakis, P. (eds.) 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0257, pp. 7:1\u20137:15. Schloss Dagstuhl- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2023). https:\/\/doi.org\/10.4230\/LIPIcs.SAND.2023.7, https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2023\/17943, ISSN 1868-8969","DOI":"10.4230\/LIPIcs.SAND.2023.7"},{"key":"19_CR11","doi-asserted-by":"publisher","unstructured":"Dudzinski, K., Walukiewicz, S.: Exact methods for the knapsack problem and its generalizations. Eur. J. Oper. Res. 28(1), 3\u201321 (1987). https:\/\/doi.org\/10.1016\/0377-2217(87)90165-2, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0377221787901652","DOI":"10.1016\/0377-2217(87)90165-2"},{"key":"19_CR12","doi-asserted-by":"publisher","unstructured":"Enright, J., Meeks, K., Mertzios, G.B., Zamaraev, V.: Deleting edges to restrict the size of an epidemic in temporal networks. J. Comput. Syst. Sci. 119, 60\u201377 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2021.01.007, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000021000155","DOI":"10.1016\/j.jcss.2021.01.007"},{"key":"19_CR13","doi-asserted-by":"publisher","unstructured":"Enright, J., Meeks, K., Skerman, F.: Assigning times to minimise reachability in temporal graphs. J. Comput. Syst. Sci. 115, 169\u2013186 (2021). https:\/\/doi.org\/10.1016\/j.jcss.2020.08.001, https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000020300799","DOI":"10.1016\/j.jcss.2020.08.001"},{"key":"19_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-319-12340-0_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T Erlebach","year":"2014","unstructured":"Erlebach, T., Hoffmann, M.: Minimum spanning tree verification under uncertainty. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 164\u2013175. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-12340-0_14"},{"key":"19_CR15","doi-asserted-by":"publisher","unstructured":"Erlebach, T., Hoffmann, M., Krizanc, D., Mihal\u2019\u00e1k, M., Raman, R.: Computing minimum spanning trees with uncertainty (2008). https:\/\/doi.org\/10.48550\/arXiv.0802.2855, arXiv:0802.2855 [cs]","DOI":"10.48550\/arXiv.0802.2855"},{"issue":"2","key":"19_CR16","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/s00453-022-01035-6","volume":"85","author":"T Erlebach","year":"2022","unstructured":"Erlebach, T., Hoffmann, M., de Lima, M.S.: Round-competitive algorithms for uncertainty problems with parallel queries. Algorithmica 85(2), 406\u2013443 (2022). https:\/\/doi.org\/10.1007\/s00453-022-01035-6","journal-title":"Algorithmica"},{"key":"19_CR17","doi-asserted-by":"publisher","unstructured":"Erlebach, T., de\u00a0Lima, M.S., Megow, N., Schl\u00f6ter, J.: Learning-augmented query policies for minimum spanning tree with uncertainty. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0244, pp. 49:1\u201349:18. Schloss Dagstuhl- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.49, https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2022\/16987, ISSN 1868-8969","DOI":"10.4230\/LIPIcs.ESA.2022.49"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Fielding, H.R., McKinley, T.J., Silk, M.J., Delahay, R.J., McDonald, R.A.: Contact chains of cattle farms in Great Britain. Roy. Soc. Open Sci. 6, 180719 (2019). https:\/\/royalsocietypublishing.org\/doi\/full\/10.1098\/rsos.180719","DOI":"10.1098\/rsos.180719"},{"key":"19_CR19","doi-asserted-by":"publisher","unstructured":"F\u00fcchsle, E., Molter, H., Niedermeier, R., Renken, M.: Delay-Robust Routes in Temporal Graphs: 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022. 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022 (2022). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.30, http:\/\/www.scopus.com\/inward\/record.url?scp=85126186124&partnerID=8YFLogxK","DOI":"10.4230\/LIPIcs.STACS.2022.30"},{"key":"19_CR20","unstructured":"Hand, S.D., Enright, J., Meeks, K.: Making life more confusing for firefighters (2022). In: 11th International Conference on Fun with Algorithms (FUN 2022), Sicily, Italy. https:\/\/eprints.gla.ac.uk\/269008\/, ISBN 9783959772327, ISSN 1868-8969"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Holme, P.: Network reachability of real-world contact sequences. Phys. Rev. E 71(4), 046119 (2005). https:\/\/journals.aps.org\/pre\/abstract\/10.1103\/PhysRevE.71.046119","DOI":"10.1103\/PhysRevE.71.046119"},{"issue":"4","key":"19_CR22","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002). https:\/\/doi.org\/10.1006\/jcss.2002.1829","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-031-48882-5_8","volume-title":"Algorithmics of Wireless Networks","author":"DC Kutner","year":"2023","unstructured":"Kutner, D.C., Larios-Jones, L.: Temporal reachability dominating sets: contagion in-temporal graphs. In: Georgiou, K., Kranakis, E. (eds.) ALGOWIN 2023. LNCS, vol. 14061, pp. 101\u2013116. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-48882-5_8"},{"key":"19_CR24","doi-asserted-by":"publisher","unstructured":"Lochet, W., Lokshtanov, D., Misra, P., Saurabh, S., Sharma, R., Zehavi, M.: Fault tolerant subgraphs with applications in kernelization. In: Vidick, T. (ed.) 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0151, pp. 47:1\u201347:22. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2020.47, https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/11732, ISSN 1868-8969","DOI":"10.4230\/LIPIcs.ITCS.2020.47"},{"issue":"4","key":"19_CR25","doi-asserted-by":"publisher","first-page":"1416","DOI":"10.1007\/s00453-018-0478-6","volume":"81","author":"GB Mertzios","year":"2019","unstructured":"Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 1416\u20131449 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0478-6","journal-title":"Algorithmica"},{"key":"19_CR26","doi-asserted-by":"publisher","unstructured":"Molter, H., Renken, M., Zschoche, P.: Temporal reachability minimization: delaying vs. deleting. In: Bonchi, F., Puglisi, S.J. (eds.) 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0202, pp. 76:1\u201376:15. Schloss Dagstuhl- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.76, https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/14516, ISSN 1868-8969","DOI":"10.4230\/LIPIcs.MFCS.2021.76"},{"key":"19_CR27","doi-asserted-by":"publisher","unstructured":"Myall, A., et al.: Characterising contact in disease outbreaks via a network model of spatial-temporal proximity (2021). https:\/\/doi.org\/10.1101\/2021.04.07.21254497, https:\/\/www.medrxiv.org\/content\/10.1101\/2021.04.07.21254497v1, pages: 2021.04.07.21254497","DOI":"10.1101\/2021.04.07.21254497"},{"key":"19_CR28","doi-asserted-by":"publisher","unstructured":"Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721\u2013732 (2014). https:\/\/doi.org\/10.14778\/2732939.2732945,","DOI":"10.14778\/2732939.2732945"},{"key":"19_CR29","doi-asserted-by":"publisher","unstructured":"Xuan, B.B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267\u2013285 (2003). https:\/\/doi.org\/10.1142\/S0129054103001728, https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001728, Publisher: World Scientific Publishing Co","DOI":"10.1142\/S0129054103001728"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2025: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-82670-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T15:25:58Z","timestamp":1754407558000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-82670-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031826696","9783031826702"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-82670-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"7 February 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interest"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bratislava","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Slovakia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 January 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 January 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"50","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sofsem.sk","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}