{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T01:41:55Z","timestamp":1779154915984,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"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\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1070\/20"],"award-info":[{"award-number":["1070\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RTG 2434"],"award-info":[{"award-number":["RTG 2434"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P020372\/1"],"award-info":[{"award-number":["EP\/P020372\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s10458-022-09583-5","type":"journal-article","created":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T13:03:57Z","timestamp":1666357437000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Interference-free walks in time: temporally disjoint paths"],"prefix":"10.1007","volume":"37","author":[{"given":"Nina","family":"Klobas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"9583_CR1","doi-asserted-by":"crossref","unstructured":"Klobas, N., Mertzios, G. B., Molter, H., Niedermeier, R., & Zschoche, P. (2021). Interference-free walks in time: Temporally disjoint paths. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4090\u20134096.","DOI":"10.24963\/ijcai.2021\/563"},{"issue":"1","key":"9583_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R. M. (1975). On the computational complexity of combinatorial problems. Networks, 5(1), 45\u201368.","journal-title":"Networks"},{"issue":"2","key":"9583_CR3","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"R Neil","year":"1985","unstructured":"Neil, R., & Seymour, P. D. (1985). Disjoint paths\u2013a survey. SIAM Journal on Algebraic and Discrete Methods, 6(2), 300\u2013305.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"1","key":"9583_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"R Neil","year":"1995","unstructured":"Neil, R., & Seymour, P. D. (1995). Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1), 65\u2013110.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9583_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Springer."},{"issue":"2","key":"9583_CR6","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K-I Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K.-I., Kobayashi, Y., & Reed, B. (2012). The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2), 424\u2013435.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"9583_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-33274-7_6","author":"R Stern","year":"2019","unstructured":"Stern, R. (2019). Multi-agent path finding - an overview. Artificial Intelligence. https:\/\/doi.org\/10.1007\/978-3-030-33274-7_6.","journal-title":"Artificial Intelligence"},{"key":"9583_CR8","doi-asserted-by":"crossref","unstructured":"Stern, R., Sturtevant, N. R., Felner, A., Koenig, S., Ma, H., Walker, T. T., Li, J., Atzmon, D., Cohen, L., Kumar, T. K. S., Boyarski, E., & Bart\u00e1k, R. (2019). Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the 12th International Symposium on Combinatorial Search (SOCS), pp. 151\u2013159.","DOI":"10.1609\/socs.v10i1.18510"},{"key":"9583_CR9","unstructured":"Almagor, S., & Lahijanian, M. (2020). Explainable multi agent path finding. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 34\u201342."},{"key":"9583_CR10","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1613\/jair.1.11734","volume":"67","author":"D Atzmon","year":"2020","unstructured":"Atzmon, D., Stern, R., Felner, A., Wagner, G., Bart\u00e1k, R., & Zhou, N.-F. (2020). Robust multi-agent path finding and executing. Journal of Artificial Intelligence Research, 67, 549\u2013579.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9583_CR11","doi-asserted-by":"crossref","unstructured":"Standley, T. S. (2010). Finding optimal solutions to cooperative pathfinding problems. In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), pp. 173\u2013178.","DOI":"10.1609\/aaai.v24i1.7564"},{"key":"9583_CR12","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D. H. K., & Nimavat, R. (2017) New hardness results for routing on disjoint paths. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 86\u201399.","DOI":"10.1145\/3055399.3055411"},{"issue":"1","key":"9583_CR13","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. (2011). Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization, 8(1), 72\u201386.","journal-title":"Discrete Optimization"},{"key":"9583_CR14","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. (2019). The parameterized complexity of the minimum shared edges problem. Journal of Computer and System Sciences, 106, 23\u201348.","journal-title":"Journal of Computer and System Sciences"},{"key":"9583_CR15","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. (2019). The complexity of routing with collision avoidance. Journal of Computer and System Sciences, 102, 69\u201386.","journal-title":"Journal of Computer and System Sciences"},{"key":"9583_CR16","doi-asserted-by":"crossref","unstructured":"Guo, L., Deng, Y., Liao, K., He, Q., Sellis, T. K., & Hu, Z. (2018). A fast algorithm for optimally finding partially disjoint shortest paths. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1456\u20131462.","DOI":"10.24963\/ijcai.2018\/202"},{"key":"9583_CR17","doi-asserted-by":"crossref","unstructured":"Tao, B., Xiao, M., & Zhao, J. (2020). Finding minimum-weight link-disjoint paths with a few common nodes. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 938\u2013945.","DOI":"10.1609\/aaai.v34i01.5441"},{"issue":"2","key":"9583_CR18","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., & Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2), 111\u2013121.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9583_CR19","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/070697781","volume":"24","author":"A Slivkins","year":"2010","unstructured":"Slivkins, A. (2010). Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM Journal of Discrete Mathematics, 24(1), 146\u2013157.","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"9583_CR20","doi-asserted-by":"publisher","first-page":"1315","DOI":"10.1007\/s10878-017-0238-6","volume":"36","author":"R Dondi","year":"2017","unstructured":"Dondi, R., & Sikora, F. (2017). Finding disjoint paths on edge-colored graphs: more tractability results. Journal of Compinatorial Optimization, 36, 1315\u20131332.","journal-title":"Journal of Compinatorial Optimization"},{"issue":"2","key":"9583_CR21","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/s10878-016-0003-2","volume":"33","author":"RF Santos","year":"2017","unstructured":"Santos, R. F., Andrioni, A., Drummond, A. C., & Xavier, E. C. (2017). Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks. Journal of Combinatorial Optimization, 33(2), 742\u2013778.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"9583_CR22","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.disopt.2012.01.002","volume":"9","author":"BY Wu","year":"2012","unstructured":"Wu, B. Y. (2012). On the maximum disjoint paths problem on edge-colored graphs. Discrete Optimization, 9(1), 50\u201357.","journal-title":"Discrete Optimization"},{"issue":"1","key":"9583_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s41109-020-00311-0","volume":"5","author":"M Bentert","year":"2020","unstructured":"Bentert, M., Himmel, A., Nichterlein, A., & Niedermeier, R. (2020). Efficient computation of optimal temporal walks under waiting-time constraints. Applied Network Science, 5(1), 73.","journal-title":"Applied Network Science"},{"key":"9583_CR24","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. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, 60\u201377.","journal-title":"Journal of Computer and System Sciences"},{"issue":"9","key":"9583_CR25","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. (2021). Finding temporal paths under waiting time constraints. Algorithmica, 83(9), 2754\u20132802.","journal-title":"Algorithmica"},{"issue":"4","key":"9583_CR26","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. (2019). Temporal network optimization subject to connectivity constraints. Algorithmica, 81(4), 1416\u20131449.","journal-title":"Algorithmica"},{"issue":"11","key":"9583_CR27","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. (2016). Efficient algorithms for temporal path computation. IEEE Transactions on Knowledge and Data Engineering, 28(11), 2927\u20132942.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"9583_CR28","unstructured":"F\u00fcchsle, E., Molter, H., Niedermeier, R., & Renken, M. (2022). Delay-robust routes in temporal graphs. In Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS)."},{"key":"9583_CR29","unstructured":"F\u00fcchsle, E., Molter, H., Niedermeier, R., & Renken, M. (2022). Temporal connectivity: Coping with foreseen and unforeseen delays. In Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND)."},{"key":"9583_CR30","unstructured":"Enright, J. A., Meeks, K., & Molter, H. (2022). Counting temporal paths. arXiv preprint arXiv:2202.12055."},{"issue":"4","key":"9583_CR31","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. (2002). Connectivity and inference problems for temporal networks. Journal of Computer and System Sciences, 64(4), 820\u2013842.","journal-title":"Journal of Computer and System Sciences"},{"key":"9583_CR32","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. (2020). Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806, 197\u2013218.","journal-title":"Theoretical Computer Science"},{"key":"9583_CR33","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. (2020). The complexity of finding separators in temporal graphs. Journal of Computer and System Sciences, 107, 72\u201392.","journal-title":"Journal of Computer and System Sciences"},{"key":"9583_CR34","doi-asserted-by":"crossref","unstructured":"Mertzios, G. B., Molter, H., & Zamaraev, V. (2019). Sliding window temporal graph coloring. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp. 7667\u20137674.","DOI":"10.1609\/aaai.v33i01.33017667"},{"key":"9583_CR35","unstructured":"Mertzios, G. B., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2020). Computing maximum matchings in temporal graphs. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science STACS."},{"key":"9583_CR36","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","volume":"107","author":"EC Akrida","year":"2020","unstructured":"Akrida, E. C., Mertzios, G. B., Spirakis, P. G., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108\u2013123.","journal-title":"Journal of Computer and System Sciences"},{"key":"9583_CR37","doi-asserted-by":"crossref","unstructured":"Hamm, T., Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2022). The complexity of temporal vertex cover in small-degree graphs. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 10193\u201310201.","DOI":"10.1609\/aaai.v36i9.21259"},{"key":"9583_CR38","unstructured":"Mertzios, G. B., Molter, H., Renken, M., Spirakis, P. G., & Zschoche, P. (2021). The complexity of transitively orienting temporal graphs. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 202, 75."},{"key":"9583_CR39","doi-asserted-by":"crossref","unstructured":"Bu\u00df, S., Molter, H., Niedermeier, R., & Rymar, M. (2020). Algorithmic aspects of temporal betweenness. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pp. 2084\u20132092.","DOI":"10.1145\/3394486.3403259"},{"issue":"1","key":"9583_CR40","first-page":"85","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C. A. (1984). A simplified NP-complete satisfiability problem. Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 8(1), 85\u201389.","journal-title":"The Journal of Combinatorial Algorithms, Informatics and Computational Sciences"},{"key":"9583_CR41","volume-title":"Digraphs - theory, algorithms and applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., & Gutin, G. Z. (2009). Digraphs - theory, algorithms and applications. Springer."},{"issue":"5","key":"9583_CR42","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. (2015). Interval scheduling and colorful independent sets. Journal of Scheduling, 18(5), 449\u2013469.","journal-title":"Journal of Scheduling"},{"key":"9583_CR43","unstructured":"Thejaswi, S., Lauri, J., & Gionis, A. (2020). Restless reachability problems in temporal graphs. arXiv preprint arXiv:2010.08423."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09583-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09583-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09583-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T07:38:30Z","timestamp":1683790710000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09583-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9583"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09583-5","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,21]]},"assertion":[{"value":"21 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"1"}}