{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T10:14:14Z","timestamp":1773483254863,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T00:00:00Z","timestamp":1661126400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["Doctoral Training account"],"award-info":[{"award-number":["Doctoral Training account"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["03421"],"award-info":[{"award-number":["03421"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T004878\/1"],"award-info":[{"award-number":["EP\/T004878\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000332","name":"Royal Society of Edinburgh","doi-asserted-by":"crossref","award":["Personal Fellowship"],"award-info":[{"award-number":["Personal Fellowship"]}],"id":[{"id":"10.13039\/501100000332","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a natural temporal analogue of Eulerian circuits and prove that, in contrast to the static case, it is<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textsc {NP}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>NP<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard to determine whether a given temporal graph is temporally Eulerian even if strong restrictions are placed on the structure of the underlying graph and each edge is active at only three times. However, we do obtain an<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\textsc {FPT}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>FPT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-algorithm with respect to a new parameter called<jats:italic>interval-membership-width<\/jats:italic>which restricts the times assigned to different edges; we believe that this parameter will be of independent interest for other temporal graph problems. Our techniques also allow us to resolve two open questions of Akrida, Mertzios and Spirakis [CIAC 2019] concerning a related problem of exploring temporal stars.<\/jats:p>","DOI":"10.1007\/s00453-022-01018-7","type":"journal-article","created":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T13:06:12Z","timestamp":1661173572000},"page":"688-716","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Edge Exploration of Temporal Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8686-2319","authenticated-orcid":false,"given":"Benjamin Merlin","family":"Bumpus","sequence":"first","affiliation":[]},{"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,22]]},"reference":[{"key":"1018_CR1","doi-asserted-by":"crossref","unstructured":"Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. In: Flocchini, P., Moura, L. (eds.) Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021. Lecture Notes in Computer Science, vol. 12757, pp. 107\u2013121. Springer (2021)","DOI":"10.1007\/978-3-030-79987-8_8"},{"issue":"3","key":"1018_CR2","doi-asserted-by":"publisher","first-page":"907","DOI":"10.1007\/s00224-017-9757-x","volume":"61","author":"EC Akrida","year":"2017","unstructured":"Akrida, E.C., G\u0105sieniec, L., Mertzios, G.B., Spirakis, P.G.: The complexity of optimal design of temporally connected graphs. Theory Comput. Syst. 61(3), 907\u2013944 (2017)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"1018_CR3","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"issue":"1","key":"1018_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s13278-017-0455-0","volume":"7","author":"A-S Himmel","year":"2017","unstructured":"Himmel, A.-S., Molter, H., Niedermeier, R., Sorge, M.: Adapting the bron-kerbosch algorithm for enumerating maximal cliques in temporal graphs. Soc. Netw. Anal. Min. 7(1), 35 (2017)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"3","key":"1018_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal networks. Phys. Rep. 519(3), 97\u2013125 (2012)","journal-title":"Phys. Rep."},{"issue":"4","key":"1018_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","volume":"12","author":"O Michail","year":"2016","unstructured":"Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Math. 12(4), 239\u2013280 (2016)","journal-title":"Internet Math."},{"key":"1018_CR7","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.jcss.2020.05.005","volume":"114","author":"EC Akrida","year":"2020","unstructured":"Akrida, E.C., Mertzios, G.B., Nikoletseas, S., Raptopoulos, C., Spirakis, P.G., Zamaraev, V.: How fast can we reach a target vertex in stochastic temporal graphs? J. Comput. Syst. Sci. 114, 65\u201383 (2020)","journal-title":"J. Comput. Syst. Sci."},{"key":"1018_CR8","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"149","volume-title":"43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)","author":"K Axiotis","year":"2016","unstructured":"Axiotis, K., Fotakis, D.: On the Size and the Approximability of Minimum Temporally Connected Subgraphs. In: Chatzigiannakis, I., Mitzenmacher, M., Rabani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, pp. 149\u2013114914. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016)"},{"issue":"3","key":"1018_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s13174-012-0073-z","volume":"3","author":"S Bhadra","year":"2012","unstructured":"Bhadra, S., Ferreira, A.: Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs. J. Internet Serv. Appl. 3(3), 269\u2013275 (2012)","journal-title":"J. Internet Serv. Appl."},{"issue":"9","key":"1018_CR10","doi-asserted-by":"publisher","first-page":"2754","DOI":"10.1007\/s00453-021-00831-w","volume":"83","author":"A Casteigts","year":"2021","unstructured":"Casteigts, A., Himmel, A., Molter, H., Zschoche, P.: Finding temporal paths under waiting time constraints. Algorithmica 83(9), 2754\u20132802 (2021)","journal-title":"Algorithmica"},{"issue":"4","key":"1018_CR11","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)","journal-title":"Algorithmica"},{"issue":"4","key":"1018_CR12","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)","journal-title":"J. Comput. Syst. Sci."},{"issue":"11","key":"1018_CR13","doi-asserted-by":"publisher","first-page":"2927","DOI":"10.1109\/TKDE.2016.2594065","volume":"28","author":"H Wu","year":"2016","unstructured":"Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., Wu, H.: Efficient algorithms for temporal path computation. IEEE Trans. Knowl. Data Eng. 28(11), 2927\u20132942 (2016)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"02","key":"1018_CR14","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"BB Xuan","year":"2003","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)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1018_CR15","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.jcss.2021.04.001","volume":"120","author":"EC Akrida","year":"2021","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Raptopoulos, C.L.: The temporal explorer who returns to the base. J. Comput. Syst. Sci. 120, 179\u2013193 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1018_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2021.01.005","volume":"119","author":"T Erlebach","year":"2021","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. J. Comput. Syst. Sci. 119, 1\u201318 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1018_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","volume":"634","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1\u201323 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1018_CR18","first-page":"128","volume":"5","author":"L Euler","year":"1741","unstructured":"Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 5, 128\u2013140 (1741)","journal-title":"Commentarii academiae scientiarum Petropolitanae"},{"key":"1018_CR19","doi-asserted-by":"crossref","unstructured":"Marino, A., Silva, A.: K\u00f6nigsberg sightseeing: Eulerian walks in temporal graphs. In: Flocchini, P., Moura, L. (eds.) Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021. Lecture Notes in Computer Science, vol. 12757, pp. 485\u2013500. Springer (2021)","DOI":"10.1007\/978-3-030-79987-8_34"},{"key":"1018_CR20","unstructured":"Mertzios, G.B., Molter, H., Niedermeier, R., Zamaraev, V., Zschoche, P.: Computing maximum matchings in temporal graphs. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020. LIPIcs, vol. 154, pp. 27\u201312714. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"1018_CR21","doi-asserted-by":"crossref","unstructured":"Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: As time goes by: Reflections on treewidth for temporal graphs. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 12160, pp. 49\u201377. Springer (2020)","DOI":"10.1007\/978-3-030-42071-0_6"},{"key":"1018_CR22","unstructured":"Hand, S., Enright, J., Meeks, K.: The temporal firefighter problem. arXiv preprint arXiv:2202.12599 (2022)"},{"key":"1018_CR23","doi-asserted-by":"crossref","unstructured":"Enright, J., Meeks, K., Molter, H.: Counting temporal paths. arXiv preprint arXiv:2202.12055 (2022)","DOI":"10.21203\/rs.3.rs-3181661\/v1"},{"key":"1018_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2010)"},{"key":"1018_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"issue":"3","key":"1018_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<125::AID-NET1>3.0.CO;2-P","volume":"28","author":"KA Berman","year":"1996","unstructured":"Berman, K.A.: Vulnerability of scheduled networks and a generalization of menger\u2019s theorem. Networks 28(3), 125\u2013134 (1996)","journal-title":"Networks"},{"key":"1018_CR27","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, San Francisco (1979)"},{"key":"1018_CR28","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. 202, pp. 76\u201317615. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021)"},{"key":"1018_CR29","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.jcss.2021.01.007","volume":"119","author":"J Enright","year":"2021","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)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01018-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01018-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01018-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T01:15:50Z","timestamp":1700961350000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01018-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,22]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1018"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01018-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,22]]},"assertion":[{"value":"15 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The first author was supported by an EPSRC doctoral training account and also received funding from the European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme (grant agreement No 803421, ReduceSearch). The second author was supported by a Royal Society of Edinburgh Personal Research Fellowship, funded by the Scottish Government, and EPSRC grant EP\/T004878\/1.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding"}}]}}