{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:59Z","timestamp":1740109319835,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T00:00:00Z","timestamp":1672704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T00:00:00Z","timestamp":1672704000000},"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\/18"],"award-info":[{"award-number":["NI 369\/18"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Addressing a quest by Gupta et al. (in: Proceedings of the 41st international colloquium on automata, languages, and programming (ICALP 2014), vol 8572 of LNCS. Springer, pp 563\u2013575, 2014), we provide a first, comprehensive study of finding a short <jats:italic>s<\/jats:italic>\u2013<jats:italic>t<\/jats:italic> path in the multistage graph model, referred to as the <jats:sc>Multistage<\/jats:sc><jats:italic>s<\/jats:italic>\u2013<jats:italic>t<\/jats:italic><jats:sc>Path<\/jats:sc> problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short\u00a0<jats:italic>s<\/jats:italic>\u2013<jats:italic>t<\/jats:italic> paths in each graph (\u201csnapshot\u201d) such that in the found path sequence the consecutive <jats:italic>s<\/jats:italic>\u2013<jats:italic>t<\/jats:italic> paths are \u201csimilar\u201d. We measure similarity by the size of the symmetric difference of either the vertex set (vertex-similarity) or the edge set (edge-similarity) of any two consecutive paths. We prove that these two variants of <jats:sc>Multistage<\/jats:sc><jats:italic>s<\/jats:italic>\u2013<jats:italic>t<\/jats:italic><jats:sc>Path<\/jats:sc> are already <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\text {NP}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mtext>NP<\/mml:mtext>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard for an input sequence of only two snapshots and maximum vertex degree four. Motivated by this fact and natural applications of this scenario e.g. in traffic route planning, we perform a parameterized complexity analysis. Among other results, for both variants, vertex- and edge-similarity, we prove parameterized hardness (<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\text {W[1]}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mtext>W[1]<\/mml:mtext>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hardness) regarding the parameter path length (solution size). As a further conceptual investigation, we then modify the multistage model by asking for <jats:italic>dissimilar<\/jats:italic> consecutive paths. As one of the main technical results (employing so-called representative sets known from non-temporal settings), we prove that dissimilarity allows for fixed-parameter tractability for the parameter solution size, contrasting with our W[1]-hardness proof of the corresponding similarity case. We also provide partially positive results concerning efficient and effective data reduction (kernelization).<\/jats:p>","DOI":"10.1007\/s00453-022-01077-w","type":"journal-article","created":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T05:05:43Z","timestamp":1672722343000},"page":"2028-2064","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Multistage s\u2013t Path: Confronting Similarity with Dissimilarity"],"prefix":"10.1007","volume":"85","author":[{"given":"Till","family":"Fluschnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Schubert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9846-0600","authenticated-orcid":false,"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,3]]},"reference":[{"key":"1077_CR1","unstructured":"Bampis, E., Escoffier, B., Lampis, M., Paschos, V.T.: Multistage matchings. In: Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), vol. 101 of LIPIcs, pp. 7:1\u20137:13. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"1077_CR2","unstructured":"Bampis, E., Escoffier, B., Schewior, K., Teiller, A.: Online multistage subset maximization problems. In: Proceedings of the 27th the Annual European Symposium on Algorithms (ESA 2020), vol. 144 of LIPIcs, pp .11:1\u201311:14. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2019a)"},{"key":"1077_CR3","unstructured":"Bampis, E., Escoffier, B., Teiller, A.: Multistage knapsack. In: Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), vol. 138 of LIPIcs, pp. 22:1\u201322:14. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2019b)"},{"key":"1077_CR4","doi-asserted-by":"publisher","unstructured":"Bampis, E., Escoffier, B., Kononov, A.V.: LP-based algorithms for multistage minimization problems. In: Proceedings of the 18th International Workshop on Approximation and Online Algorithms (WAOA\u00a02020), vol. 12806 of LNCS, pp. 1\u201315. Springer (2020). https:\/\/doi.org\/10.1007\/978-3-030-80879-2_1","DOI":"10.1007\/978-3-030-80879-2_1"},{"key":"1077_CR5","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\u201326 (2020)","journal-title":"Appl. Netw. Sci."},{"issue":"8","key":"1077_CR6","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"1077_CR7","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."},{"key":"1077_CR8","doi-asserted-by":"publisher","unstructured":"Bredereck, R., Fluschnik, T., Kaczmarczyk, A.: When votes change and committees should (not). In: Proceedings of the 31th International Joint Conference on Artificial Intelligence (IJCAI\u00a02022), pp. 144\u2013150. ijcai.org (2022). https:\/\/doi.org\/10.24963\/ijcai.2022\/21","DOI":"10.24963\/ijcai.2022\/21"},{"key":"1077_CR9","doi-asserted-by":"crossref","unstructured":"Bu\u00df, S., Molter, H., Niedermeier, R., Rymar, M.: Algorithmic aspects of temporal betweenness. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2020), pp. 2084\u20132092 (2020)","DOI":"10.1145\/3394486.3403259"},{"issue":"9","key":"1077_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.-S., Molter, H., Zschoche, P.: Finding temporal paths under waiting time constraints. Algorithmica 83(9), 2754\u20132802 (2021). https:\/\/doi.org\/10.1007\/s00453-021-00831-w","journal-title":"Algorithmica"},{"issue":"6","key":"1077_CR11","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004). https:\/\/doi.org\/10.1137\/S0097539702418498","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1077_CR12","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1137\/130927115","volume":"44","author":"A Drucker","year":"2015","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. SIAM J. Comput. 44(5), 1443\u20131479 (2015)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1077_CR13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series\u2013parallel networks. J. Math. Anal. Appl. 10(2), 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"key":"1077_CR14","doi-asserted-by":"crossref","unstructured":"Eisenstat, D., Mathieu, C., Schabanel, N.: Facility location in evolving metrics. In: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), vol. 8572 of LNCS, pp. 459\u2013470. Springer (2014)","DOI":"10.1007\/978-3-662-43951-7_39"},{"issue":"6","key":"1077_CR15","doi-asserted-by":"publisher","first-page":"1857","DOI":"10.1007\/s00453-017-0311-7","volume":"80","author":"J Enright","year":"2018","unstructured":"Enright, J., Meeks, K.: Deleting edges to restrict the size of an epidemic: a new application for treewidth. Algorithmica 80(6), 1857\u20131889 (2018)","journal-title":"Algorithmica"},{"key":"1077_CR16","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). https:\/\/doi.org\/10.1016\/j.jcss.2021.01.007","journal-title":"J. Comput. Syst. Sci."},{"key":"1077_CR17","unstructured":"Erlebach, T., Spooner, J.T.: Faster exploration of degree-bounded temporal graphs. In: Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), vol. 117 of LIPIcs, pp. 36:1\u201336:13. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"1077_CR18","unstructured":"Erlebach, T., Kammer, F., Luo, K., Sajenko, A., Spooner, J.T.: Two moves per time step make a difference. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol. 132 of LIPIcs, pp. 141:1\u2013141:14. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1077_CR19","doi-asserted-by":"publisher","unstructured":"Fluschnik, T.: A multistage view on 2-satisfiability. In: Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC\u00a02021), vol. 12701 of LNCS, pp. 231\u2013244. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-75242-2_16","DOI":"10.1007\/978-3-030-75242-2_16"},{"key":"1077_CR20","doi-asserted-by":"publisher","unstructured":"Fluschnik, T., Kunz, P.: Bipartite temporal graphs and the parameterized complexity of multistage 2-coloring. In: Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND\u00a02022), vol. 221 of LIPIcs, pp. 16:1\u201316:18. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPIcs.SAND.2022.16","DOI":"10.4230\/LIPIcs.SAND.2022.16"},{"key":"1077_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.jcss.2018.12.002","volume":"106","author":"T Fluschnik","year":"2019","unstructured":"Fluschnik, T., Kratsch, S., Niedermeier, R., Sorge, M.: The parameterized complexity of the minimum shared edges problem. J. Comput. Syst. Sci. 106, 23\u201348 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"1077_CR22","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.jcss.2019.01.001","volume":"102","author":"T Fluschnik","year":"2019","unstructured":"Fluschnik, T., Morik, M., Sorge, M.: The complexity of routing with collision avoidance. J. Comput. Syst. Sci. 102, 69\u201386 (2019)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1077_CR23","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/s00224-022-10069-w","volume":"66","author":"T Fluschnik","year":"2022","unstructured":"Fluschnik, T., Niedermeier, R., Rohm, V., Zschoche, P.: Multistage vertex cover. Theory Comput. Syst. 66(2), 454\u2013483 (2022). https:\/\/doi.org\/10.1007\/s00224-022-10069-w","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"1077_CR24","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","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-29:60 (2016)","journal-title":"J. ACM"},{"issue":"1","key":"1077_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"1077_CR26","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, New York (1979)"},{"key":"1077_CR27","first-page":"2142","volume":"7","author":"S Ghariblou","year":"2017","unstructured":"Ghariblou, S., Salehi, M., Magnani, M., Jalili, M.: Shortest paths in multiplex networks. Nat. Sci. Rep. 7, 2142 (2017)","journal-title":"Nat. Sci. Rep."},{"issue":"1","key":"1077_CR28","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.disopt.2010.09.009","volume":"8","author":"PA Golovach","year":"2011","unstructured":"Golovach, P.A., Thilikos, D.M.: Paths of bounded length and their cuts: parameterized complexity and algorithms. Discrete Optim. 8(1), 72\u201386 (2011)","journal-title":"Discrete Optim."},{"key":"1077_CR29","doi-asserted-by":"crossref","unstructured":"Gupta, A., Talwar, K., Wieder, U.: Changing bases: multistage optimization for matroids and matchings. In: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), vol. 8572 of LNCS, pp. 563\u2013575. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_47"},{"key":"1077_CR30","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2012.12.049","volume":"494","author":"S Hartung","year":"2013","unstructured":"Hartung, S., Niedermeier, R.: Incremental list coloring of graphs, parameterized by conservation. Theor. Comput. Sci. 494, 86\u201398 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"1077_CR31","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2021.04.002","volume":"868","author":"K Heeger","year":"2021","unstructured":"Heeger, K., Himmel, A.-S., Kammer, F., Niedermeier, R., Renken, M., Sajenko, A.: Multistage graph problems on a global budget. Theor. Comput. Sci. 868, 46\u201364 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.04.002","journal-title":"Theor. Comput. Sci."},{"volume-title":"Temporal Networks","year":"2013","key":"1077_CR32","unstructured":"Holme, P., Saram\u00e4ki, J. (eds.): Temporal Networks. Springer, Berlin (2013)"},{"volume-title":"Temporal Network Theory","year":"2019","key":"1077_CR33","unstructured":"Holme, P., Saram\u00e4ki, J. (eds.): Temporal Network Theory. Springer, Berlin (2019)"},{"key":"1077_CR34","doi-asserted-by":"publisher","unstructured":"Kellerhals, L., Renken, M., Zschoche, P.: Parameterized algorithms for diverse multistage problems. In: Proceedings of the 29th Annual European Symposium on Algorithms (ESA\u00a02021), vol. 204, pp. 55:1\u201355:17. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.55","DOI":"10.4230\/LIPIcs.ESA.2021.55"},{"issue":"4","key":"1077_CR35","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.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"1077_CR36","doi-asserted-by":"publisher","unstructured":"Klobas, N., Mertzios, G.B., Molter, H., Niedermeier, R., Zschoche, P.: Interference-free walks in time: temporally disjoint paths. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI\u00a02021), pp. 4090\u20134096. ijcai.org (2021). https:\/\/doi.org\/10.24963\/ijcai.2021\/563","DOI":"10.24963\/ijcai.2021\/563"},{"issue":"1","key":"1077_CR37","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":"1077_CR38","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.comnet.2018.12.010","volume":"150","author":"M Latapy","year":"2019","unstructured":"Latapy, M., Fiore, M., Ziviani, A.: Link streams: methods and applications. Comput. Netw. 150, 263\u2013265 (2019)","journal-title":"Comput. Netw."},{"issue":"44","key":"1077_CR39","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."},{"issue":"4","key":"1077_CR40","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":"1077_CR41","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Discrete Math. 25, 239\u2013254 (1985)","journal-title":"Discrete Math."},{"key":"1077_CR42","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)"},{"key":"1077_CR43","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC 1978), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"278","key":"1077_CR44","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1090\/S0025-5718-2011-02542-1","volume":"81","author":"T Tao","year":"2012","unstructured":"Tao, T., Croot, E., III., Helfgott, H.: Deterministic methods to find primes. Math. Comput. 81(278), 1233\u20131246 (2012)","journal-title":"Math. Comput."},{"issue":"11","key":"1077_CR45","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., Hejun, W.: Efficient algorithms for temporal path computation. IEEE Trans. Knowl. Data Eng. 28(11), 2927\u20132942 (2016)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"1077_CR46","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C-K Yap","year":"1983","unstructured":"Yap, C.-K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"1077_CR47","doi-asserted-by":"publisher","unstructured":"Zschoche, P.: Restless temporal path parameterized above lower bounds. CoRR (2022). https:\/\/doi.org\/10.48550\/arXiv.2203.15862","DOI":"10.48550\/arXiv.2203.15862"},{"key":"1077_CR48","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 small 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-022-01077-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01077-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01077-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T05:58:29Z","timestamp":1687499909000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01077-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,3]]},"references-count":48,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["1077"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01077-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2023,1,3]]},"assertion":[{"value":"5 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2023","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 authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}