{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T11:39:38Z","timestamp":1771933178540,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:00:00Z","timestamp":1661385600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:00:00Z","timestamp":1661385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"MUR, PRIN","doi-asserted-by":"publisher","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Dipartimento di Statistica, Informatica, Applicazioni, UNIFI","award":["GRANTED"],"award-info":[{"award-number":["GRANTED"]}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["303803\/2020-7"],"award-info":[{"award-number":["303803\/2020-7"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["437841\/2018-9"],"award-info":[{"award-number":["437841\/2018-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"name":"STIC-AMSUD","award":["360\/2019 - 88881.197438\/2018-01"],"award-info":[{"award-number":["360\/2019 - 88881.197438\/2018-01"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,3]]},"abstract":"Abstract<\/jats:title>An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph G<\/jats:italic> at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of K\u00f6nigsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph $$\\varvec{(G,\\lambda )}$$<\/jats:tex-math>\n \n (<\/mml:mo>\n G<\/mml:mi>\n ,<\/mml:mo>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, with $$\\varvec{\\lambda : E(G)}\\varvec{\\rightarrow } \\varvec{2}^{\\varvec{[\\tau ]}}$$<\/jats:tex-math>\n \n \n \u03bb<\/mml:mi>\n :<\/mml:mo>\n E<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u2192<\/mml:mo>\n <\/mml:mrow>\n \n \n 2<\/mml:mn>\n <\/mml:mrow>\n \n [<\/mml:mo>\n \u03c4<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, an edge $$\\varvec{e}\\varvec{\\in } \\varvec{E(G)}$$<\/jats:tex-math>\n \n \n e<\/mml:mi>\n <\/mml:mrow>\n \n \u2208<\/mml:mo>\n <\/mml:mrow>\n \n E<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is available only at the times specified by $$\\varvec{\\lambda (e)}\\varvec{\\subseteq } \\varvec{[\\tau ]}$$<\/jats:tex-math>\n \n \n \u03bb<\/mml:mi>\n (<\/mml:mo>\n e<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u2286<\/mml:mo>\n <\/mml:mrow>\n \n [<\/mml:mo>\n \u03c4<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether $$\\varvec{(G,\\lambda )}$$<\/jats:tex-math>\n \n (<\/mml:mo>\n G<\/mml:mi>\n ,<\/mml:mo>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> has a temporal walk or trail is polynomial, while deciding whether it has a local trail is $$\\varvec{\\texttt {NP}}$$<\/jats:tex-math>\n \n NP<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete even if $$\\varvec{\\tau = 2}$$<\/jats:tex-math>\n \n \u03c4<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In contrast, in the general case, solving any of these problems is $$\\varvec{\\texttt {NP}}$$<\/jats:tex-math>\n \n NP<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete, even under very strict hypotheses. We finally give $$\\varvec{\\texttt {XP}}$$<\/jats:tex-math>\n \n XP<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> algorithms parametrized by $$\\varvec{\\tau }$$<\/jats:tex-math>\n \n \u03c4<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for walks, and by $$\\varvec{\\tau +tw(G)}$$<\/jats:tex-math>\n \n \u03c4<\/mml:mi>\n +<\/mml:mo>\n t<\/mml:mi>\n w<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for trails and local trails, where $$\\varvec{tw(G)}$$<\/jats:tex-math>\n \n t<\/mml:mi>\n w<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> refers to the treewidth of $$\\varvec{G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00453-022-01021-y","type":"journal-article","created":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T07:02:32Z","timestamp":1661410952000},"page":"805-830","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Eulerian Walks in Temporal Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9854-7885","authenticated-orcid":false,"given":"Andrea","family":"Marino","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8917-0564","authenticated-orcid":false,"given":"Ana","family":"Silva","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,25]]},"reference":[{"key":"1021_CR1","doi-asserted-by":"crossref","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G.: The temporal explorer who returns to the base. In: Heggernes, P. (ed.) Algorithms and Complexity\u201411th International Conference, CIAC 2019, Rome, Italy, May 27\u201329, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11485, pp. 13\u201324. Springer (2019)","DOI":"10.1007\/978-3-030-17402-6_2"},{"key":"1021_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1155\/2013\/721051","volume":"2013","author":"S Arumugam","year":"2013","unstructured":"Arumugam, S., Hamid, I., Abraham, V.: Decomposition of graphs into paths and cycles. J. Discrete Math. 2013, 1\u20136 (2013)","journal-title":"J. Discrete Math."},{"issue":"2","key":"1021_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., et al.: A $$c^k n$$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"key":"1021_CR4","unstructured":"Borgnat, P., Fleury, E., Guillaume, J., et\u00a0al.: Evolving networks. In: Mining Massive Data Sets for Security, pp. 198\u2013203 (2007)"},{"key":"1021_CR5","doi-asserted-by":"crossref","unstructured":"Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. In: Flocchini, P., Moura, L. (eds) Combinatorial Algorithms\u201432nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5\u20137, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12757, pp. 107\u2013121. Springer (2021)","DOI":"10.1007\/978-3-030-79987-8_8"},{"issue":"5","key":"1021_CR6","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., et al.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"issue":"1","key":"1021_CR7","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10100-018-0598-8","volume":"28","author":"MK \u00c7odur","year":"2020","unstructured":"\u00c7odur, M.K., Y\u0131lmaz, M.: A time-dependent hierarchical Chinese postman problem. CEJOR 28(1), 337\u2013366 (2020)","journal-title":"CEJOR"},{"issue":"1","key":"1021_CR8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s00453-012-9667-x","volume":"68","author":"M Cygan","year":"2014","unstructured":"Cygan, M., Marx, D., Pilipczuk, M., et al.: Parameterized complexity of Eulerian deletion problems. Algorithmica 68(1), 41\u201361 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"1021_CR9","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., et al.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1021_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1002\/net.3230170304","volume":"17","author":"M Dror","year":"1987","unstructured":"Dror, M., Stern, H., Trudeau, P.: Postman tour on a graph with precedence relation on arcs. Networks 17(3), 283\u2013294 (1987)","journal-title":"Networks"},{"key":"1021_CR11","unstructured":"Erlebach, T., Spooner, J.T.: Faster exploration of degree-bounded temporal graphs. In: Potapov I, Spirakis PG, Worrell J (eds) 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27\u201331, 2018, Liverpool, UK, LIPIcs, vol 117. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 36:1\u201336:13 (2018)"},{"key":"1021_CR12","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Spooner, J.T.: Non-strict temporal exploration. In: Richa, A.W., Scheideler, C. (eds) Structural Information and Communication Complexity\u201427th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29\u2013July 1, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12156, pp. 129\u2013145. Springer (2020)","DOI":"10.1007\/978-3-030-54921-3_8"},{"key":"1021_CR13","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: 42nd International Colloquium on Automata, Languages, and Programming\u2014ICALP 2015, Kyoto, Japan, Lecture Notes in Computer Science, vol. 9134, pp. 444\u2013455. Springer (2015)","DOI":"10.1007\/978-3-662-47672-7_36"},{"key":"1021_CR14","unstructured":"Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae pp. 128\u2013140 (1741)"},{"issue":"2","key":"1021_CR15","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1137\/130936816","volume":"28","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A.: Long circuits and large Euler subgraphs. SIAM J. Discret. Math. 28(2), 878\u2013892 (2014)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"1021_CR16","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"key":"1021_CR17","doi-asserted-by":"crossref","unstructured":"G\u00f3mez, R., Wakabayashi, Y.: Covering a graph with nontrivial vertex-disjoint paths: Existence and optimization. In: Brandst\u00e4dt, A., K\u00f6hler, E., Meer, K. (eds) Graph-Theoretic Concepts in Computer Science\u201444th International Workshop, WG 2018, Cottbus, Germany, June 27\u201329, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11159, pp. 228\u2013238. Springer (2018)","DOI":"10.1007\/978-3-030-00256-5_19"},{"key":"1021_CR18","first-page":"273","volume":"1962","author":"M Guan","year":"1960","unstructured":"Guan, M.: Graphic programming using odd or even points. Acta Mathematica Sinica (in Chinese) 10:263\u2013266. Translated in Chinese Mathematics 1. Am. Math. Soc. 1962, 273\u2013277 (1960)","journal-title":"Am. Math. Soc."},{"key":"1021_CR19","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. In: Yao FF, Luks EM (eds) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21\u201323, pp. 504\u2013513 . ACM, Portland (2000)","DOI":"10.1145\/335305.335364"},{"key":"1021_CR20","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer (1994)","DOI":"10.1007\/BFb0045375"},{"issue":"1","key":"1021_CR21","doi-asserted-by":"publisher","first-page":"61:1","DOI":"10.1007\/s13278-018-0537-7","volume":"8","author":"M Latapy","year":"2018","unstructured":"Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min. 8(1), 61:1-61:29 (2018)","journal-title":"Soc. Netw. Anal. Min."},{"key":"1021_CR22","unstructured":"Manuel, P.: Revisiting path-type covering and partitioning problems. arXiv:1807.10613 (2018)"},{"key":"1021_CR23","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, Ottawa, ON, Canada, July 5\u20137, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12757, pp. 485\u2013500. Springer (2021)","DOI":"10.1007\/978-3-030-79987-8_34"},{"issue":"4","key":"1021_CR24","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":"1021_CR25","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. Theoret. Comput. Sci. 634, 1\u201323 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"1021_CR26","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Some problems on dynamic\/periodic graphs. In: Progress in Combinatorial Optimization, pp. 273\u2013293. Elsevier (1984)","DOI":"10.1016\/B978-0-12-566780-7.50022-2"},{"key":"1021_CR27","first-page":"833","volume":"8","author":"J Sun","year":"2011","unstructured":"Sun, J., Tan, G., Qu, H.: Dynamic programming algorithm for the time dependent Chinese postman problem. J. Inf. Comput. Sci. 8, 833\u2013841 (2011)","journal-title":"J. Inf. Comput. Sci."},{"issue":"3\u20134","key":"1021_CR28","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/S0898-1221(02)00156-6","volume":"44","author":"HF Wang","year":"2002","unstructured":"Wang, H.F., Wen, Y.P.: Time-constrained Chinese postman problems. Comput. Math. Appl. 44(3\u20134), 375\u2013387 (2002)","journal-title":"Comput. Math. Appl."},{"key":"1021_CR29","volume-title":"Introduction to Graph Theory","author":"D West","year":"1996","unstructured":"West, D.: Introduction to Graph Theory, vol. 2. Prentice Hall, Upper Saddle River (1996)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01021-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01021-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01021-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,3]],"date-time":"2023-03-03T15:06:03Z","timestamp":1677855963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01021-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,25]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1021"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01021-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,25]]},"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":"25 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}