{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T19:04:44Z","timestamp":1775070284603,"version":"3.50.1"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/17"],"award-info":[{"award-number":["NI 369\/17"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/16"],"award-info":[{"award-number":["NI 369\/16"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE25-0009-03"],"award-info":[{"award-number":["ANR-16-CE25-0009-03"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or <jats:italic>temporal<\/jats:italic>, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, referred to as <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varDelta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0394<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-<jats:italic>restless temporal paths<\/jats:italic>. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the \u201crestless variant\u201d of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the <jats:italic>distance to disjoint path<\/jats:italic> of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three <jats:italic>kinds<\/jats:italic> of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called <jats:italic>timed feedback vertex number<\/jats:italic>, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.<\/jats:p>","DOI":"10.1007\/s00453-021-00831-w","type":"journal-article","created":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T10:04:25Z","timestamp":1622801065000},"page":"2754-2802","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":49,"title":["Finding Temporal Paths Under Waiting Time Constraints"],"prefix":"10.1007","volume":"83","author":[{"given":"Arnaud","family":"Casteigts","sequence":"first","affiliation":[]},{"given":"Anne-Sophie","family":"Himmel","sequence":"additional","affiliation":[]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9846-0600","authenticated-orcid":false,"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,4]]},"reference":[{"key":"831_CR1","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1007\/s00453-020-00681-y","volume":"82","author":"A Akanksha","year":"2020","unstructured":"Akanksha, A., Pallavi, J., Lawqueen, K., Saket, S.: Parameterized complexity of conflict-free matchings and paths. Algorithmica 82, 1939\u20131965 (2020)","journal-title":"Algorithmica"},{"key":"831_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00856-6","volume-title":"Proofs from the Book","author":"M Aigner","year":"2010","unstructured":"Aigner, M., Ziegler, G.M., Hofmann, K.H., Paul ErdosPaul ErdosErdos, P.: Proofs from the Book. Springer, Berlin (2010)"},{"issue":"3","key":"831_CR3","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."},{"key":"831_CR4","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.jcss.2019.02.003","volume":"103","author":"EC Akrida","year":"2019","unstructured":"Akrida, E.C., Czyzowicz, J., G\u0105sieniec, L., Kuszner, \u0141., Spirakis, P.G.: Temporal flows in temporal networks. J. Comput. Syst. Sci. 103, 46\u201360 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"831_CR5","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":"831_CR6","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201921), pp. 522\u2013539. SIAM (2021)","DOI":"10.1137\/1.9781611976465.32"},{"key":"831_CR7","unstructured":"Axiotis, K., Fotakis, D.: On the size and the approximability of minimum temporally connected subgraphs. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u00a0\u201916), pp. 149:1\u2013149:14 (2016)"},{"key":"831_CR8","volume-title":"Network Science","author":"A-L Barab\u00e1si","year":"2016","unstructured":"Barab\u00e1si, A.-L.: Network Science. Cambridge University Press, Cambridge (2016)"},{"key":"831_CR9","unstructured":"Bentert, M., Dittmann, A., Kellerhals, L., Nichterlein, A., Niedermeier, R.: An adaptive version of Brandes\u2019 algorithm for betweenness centrality. In: 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16\u201319, 2018, Jiaoxi, Yilan, Taiwan, pp. 36:1\u201336:13 (2018)"},{"issue":"1","key":"831_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-018-0595-8","volume":"22","author":"M Bentert","year":"2019","unstructured":"Bentert, M., van Bevern, R., Niedermeier, R.: Inductive $$k$$-independent graphs and $$c$$-colorable subgraphs in scheduling: a review. J. Sched. 22(1), 3\u201320 (2019)","journal-title":"J. Sched."},{"issue":"1","key":"831_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-020-00311-0","volume":"5","author":"M Bentert","year":"2020","unstructured":"Bentert, M., Himmel, A.-S., Nichterlein, A., Niedermeier, R.: Efficient computation of optimal temporal walks under waiting-time constraints. Appl. Netw. Sci. 5(1), 1\u201326 (2020)","journal-title":"Appl. Netw. Sci."},{"issue":"3","key":"831_CR12","first-page":"125","volume":"28","author":"KA Berman","year":"1996","unstructured":"Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger\u2019s theorem. Netw. An Int. J. 28(3), 125\u2013134 (1996)","journal-title":"Netw. An Int. J."},{"issue":"5","key":"831_CR13","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s10951-014-0398-5","volume":"18","author":"R van Bevern","year":"2015","unstructured":"van Bevern, R., Mnich, M., Niedermeier, R., Weller, M.: Interval scheduling and colorful independent sets. J. Sched. 18(5), 449\u2013469 (2015)","journal-title":"J. Sched."},{"key":"831_CR14","doi-asserted-by":"crossref","unstructured":"Bhadra, S., Ferreira, F.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: International Conference on Ad-Hoc Networks and Wireless, pp. 259\u2013270. Springer (2003)","DOI":"10.1007\/978-3-540-39611-6_23"},{"issue":"1","key":"831_CR15","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20134","key":"831_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/176454.176484","volume":"2","author":"P Briggs","year":"1993","unstructured":"Briggs, P., Torczon, L.: An efficient representation for sparse sets. ACM Lett. Program. Lang. Syst. (LOPLAS) 2(1\u20134), 59\u201369 (1993)","journal-title":"ACM Lett. Program. Lang. Syst. (LOPLAS)"},{"issue":"02","key":"831_CR17","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B-M Bui-Xuan","year":"2003","unstructured":"Bui-Xuan, B.-M., 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."},{"issue":"5","key":"831_CR18","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 Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"831_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2015.04.004","volume":"590","author":"A Casteigts","year":"2015","unstructured":"Casteigts, A., Flocchini, P., Godard, E., Santoro, N., Yamashita, M.: On the expressivity of time-varying graphs. Theor. Comput. Sci. 590, 27\u201337 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"831_CR20","unstructured":"Casteigts, A., Peters, J., Schoeters, J.: Temporal cliques admit sparse spanners. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u00a0\u201919), volume 132 of LIPIcs, pp. 134:1\u2013134:14. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"831_CR21","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, London (2009)"},{"issue":"1","key":"831_CR22","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1137\/110843071","volume":"27","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Subset feedback vertex set is fixed-parameter tractable. SIAM J. Discrete Math. 27(1), 290\u2013309 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"831_CR23","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., Pilipczuk, M., Saurabh, S., Marx, D., Pilipczuk, M.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"831_CR24","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 5th edn, volume 173 of Graduate Texts in Mathematics. Springer, Berlin (2016)","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"831_CR25","doi-asserted-by":"crossref","unstructured":"Eames, K.T.D., Keeling, M.J. (2003) Contact tracing and disease control. Proc. R. Soc. Lond. Ser. B Biol. Sci. 270(1533):2565\u20132571","DOI":"10.1098\/rspb.2003.2554"},{"key":"831_CR26","unstructured":"Enright, J., Meeks, K., Mertzios, G., Zamaraev, V.: Deleting edges to restrict the size of an epidemic in temporal networks. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS\u00a0\u201919), volume 138 of LIPIcs, pp. 57:1\u201357:15. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"issue":"4","key":"831_CR27","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231\u20131252 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"831_CR28","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"831_CR29","doi-asserted-by":"crossref","unstructured":"Ferretti, L., Wymant, C., Kendall, M., Zhao, L., Nurtay, A., Abeler-D\u00f6rner, L., Parker, M., Bonsall, D., Fraser, C.: Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing. Science (2020)","DOI":"10.1101\/2020.03.08.20032946"},{"key":"831_CR30","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.tcs.2019.03.031","volume":"806","author":"T Fluschnik","year":"2020","unstructured":"Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: Temporal graph classes: a view through temporal separators. Theor. Comput. Sci. 806, 197\u2013218 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"831_CR31","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4):29:1\u201329:60 (2016)","DOI":"10.1145\/2886094"},{"key":"831_CR32","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative families of product families. ACM Trans. Algorithms 13(3), 36:1\u201336:29 (2017)","DOI":"10.1145\/3039243"},{"key":"831_CR33","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"831_CR34","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: Blasting through the information theoretic barrier with fusion trees. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC\u00a0\u201990), pp. 1\u20137 (1990)","DOI":"10.1145\/100216.100217"},{"issue":"1","key":"831_CR35","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combin. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"831_CR36","doi-asserted-by":"crossref","unstructured":"Haag, R., Molter, H., Niedermeier, R., Renken, M.: Feedback edge sets in temporal graphs. In: Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u00a0\u201920), volume 12301 of Lecture Notes in Computer Science, pp. 200\u20132012. Springer (2020)","DOI":"10.1007\/978-3-030-60440-0_16"},{"issue":"9","key":"831_CR37","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"P Holme","year":"2015","unstructured":"Holme, P.: Modern temporal network theory: a colloquium. Eur. Phys. J. B 88(9), 234 (2015)","journal-title":"Eur. Phys. J. B"},{"key":"831_CR38","doi-asserted-by":"crossref","unstructured":"Holme, P.: Temporal network structures controlling disease spreading. Phys. Rev. E 94(2), 022305 (2016)","DOI":"10.1103\/PhysRevE.94.022305"},{"key":"831_CR39","doi-asserted-by":"crossref","unstructured":"Holme, P., Saram\u00e4ki, J. (eds.): Temporal Network Theory. Springer, Berlin (2019)","DOI":"10.1007\/978-3-030-23495-9"},{"issue":"2","key":"831_CR40","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"831_CR41","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"831_CR42","doi-asserted-by":"publisher","first-page":"1377","DOI":"10.1137\/140962838","volume":"45","author":"Y Iwata","year":"2016","unstructured":"Iwata, Y., Wahlstr\u00f6m, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377\u20131411 (2016)","journal-title":"SIAM J. Comput."},{"key":"831_CR43","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer, Berlin (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"831_CR44","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":"772","key":"831_CR45","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1098\/rspa.1927.0118","volume":"115","author":"WO Kermack","year":"1927","unstructured":"Kermack, W.O., McKendrick, A.G.: A contribution to the mathematical theory of epidemics. Proc. R. Soc. Lond. Ser. A 115(772), 700\u2013721 (1927)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"issue":"1","key":"831_CR46","doi-asserted-by":"publisher","first-page":"61","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 (2018)","journal-title":"Soc. Netw. Anal. Min."},{"key":"831_CR47","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S.:. Deterministic truncation of linear matroids. ACM Trans. Algorithms 14(2), 14:1\u201314:20 (2018a)","DOI":"10.1145\/3170444"},{"key":"831_CR48","unstructured":"Lokshtanov, D., Misra, P., Panolan, F., Saurabh, S., Zehavi, M.: Quasipolynomial representation of transversal matroids with applications in parameterized complexity. In: Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS\u00a0\u201918), pp. 32:1\u201332:13 (2018b)"},{"issue":"44","key":"831_CR49","doi-asserted-by":"publisher","first-page":"4471","DOI":"10.1016\/j.tcs.2009.07.027","volume":"410","author":"D Marx","year":"2009","unstructured":"Marx, D.: A parameterized view on matroid optimization problems. Theor. Comput. Sci. 410(44), 4471\u20134479 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"831_CR50","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 1416\u20131449 (2019)","DOI":"10.1007\/s00453-018-0478-6"},{"issue":"4","key":"831_CR51","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":"831_CR52","unstructured":"Molter, H.: Classic graph problems made temporal\u2014a parameterized complexity analysis. Ph.D. thesis, Technische Universit\u00e4t Berlin, December 2020. http:\/\/dx.doi.org\/10.14279\/depositonce-10551"},{"key":"831_CR53","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Mendez, P.O. De.: Sparsity: Graphs, Structures, and Algorithms. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"831_CR54","doi-asserted-by":"crossref","unstructured":"Newman, M.E.J.: Networks. Oxford University Press, Oxford (2018)","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"831_CR55","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)"},{"key":"831_CR56","doi-asserted-by":"crossref","unstructured":"Pan, R.K., Saram\u00e4ki, J.: Path lengths, correlations, and centrality in temporal networks. Phys. Rev. E 84(1), 016105 (2011)","DOI":"10.1103\/PhysRevE.84.016105"},{"key":"831_CR57","unstructured":"Sorge, M., Weller, M. et\u00a0al.: The graph parameter hierarchy, 2018. https:\/\/manyu.pro\/assets\/parameter-hierarchy.pdf (2020)"},{"key":"831_CR58","doi-asserted-by":"crossref","unstructured":"Tao, T., Croot\u00a0III, E., Helfgott, H.: Deterministic methods to find primes. Math. Comput. 81(278), 1233\u20131246 (2012)","DOI":"10.1090\/S0025-5718-2011-02542-1"},{"issue":"1","key":"831_CR59","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8(1), 85\u201389 (1984)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"831_CR60","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $$k$$ in $${O}^*(2^k)$$ time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"11","key":"831_CR61","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."},{"key":"831_CR62","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.jcss.2019.07.006","volume":"107","author":"P Zschoche","year":"2020","unstructured":"Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding separators in temporal graphs. J. Comput. Syst. Sci. 107, 72\u201392 (2020)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00831-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00831-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00831-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T13:20:53Z","timestamp":1633008053000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00831-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,4]]},"references-count":62,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["831"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00831-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,4]]},"assertion":[{"value":"23 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}