{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T14:52:01Z","timestamp":1743000721937,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031744976"},{"type":"electronic","value":"9783031744983"}],"license":[{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-74498-3_17","type":"book-chapter","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T11:02:30Z","timestamp":1729335750000},"page":"240-254","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Partially Disjoint Shortest Paths and\u00a0Near-Shortest Paths Trees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-4211-4182","authenticated-orcid":false,"given":"Yefim","family":"Dinitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5418-6670","authenticated-orcid":false,"given":"Shlomi","family":"Dolev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0620-3303","authenticated-orcid":false,"given":"Manish","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-5750-2177","authenticated-orcid":false,"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,20]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Akhmedov, M.: Faster 2-disjoint-shortest-paths algorithm. In: Computer Science\u2014Theory and Applications\u201415th International Computer Science Symposium in Russia (CSR 2020), pp. 103\u2013116 (2020)","DOI":"10.1007\/978-3-030-50026-9_7"},{"key":"17_CR2","unstructured":"Bentert, M., Nichterlein, A., Renken, M., Zschoche, P.: Using a geometric lens to find k disjoint shortest paths. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 26:1\u201326:14 (2021)"},{"key":"17_CR3","unstructured":"B\u00e9rczi, K., Kobayashi, Y.: The directed disjoint shortest paths problem. In: 25th Annual European Symposium on Algorithms (ESA 2017), pp. 13:1\u201313:13 (2017)"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Chondrogiannis, T., Bouros, P., Gamper, J., Leser, U.: Alternative routing: k-shortest paths with limited overlap. In: 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 68:1\u201368:4 (2015)","DOI":"10.1145\/2820783.2820858"},{"key":"17_CR5","unstructured":"Chondrogiannis, T., Bouros, P., Gamper, J., Leser, U.: Exact and approximate algorithms for finding k-shortest paths with limited overlap. In: 20th International Conference on Extending Database Technology (EDBT 2017), pp. 414\u2013425 (2017)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Deng, Y., Guo, L., Huang, P.: Exact algorithms for finding partial edge-disjoint paths. In: 24th International Computing and Combinatorics Conference (COCOON 2018), pp. 14\u201325 (2018)","DOI":"10.1007\/978-3-319-94776-1_2"},{"key":"17_CR7","unstructured":"Dinitz, Y.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Dokl. 11, 1277\u20131280 (1970)"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Dolev, S., Kumar, M.: Polynomial time $$k$$-shortest multi-criteria prioritized and all-criteria-disjoint paths. In: Cyber Security Cryptography and Machine Learning\u20145th International Symposium (CSCML 2021). Lecture Notes in Computer Science. Springer (2021)","DOI":"10.1007\/978-3-030-78086-9_20"},{"issue":"2","key":"17_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0166-218X(97)00121-2","volume":"85","author":"T Eilam-Tzoreff","year":"1998","unstructured":"Eilam-Tzoreff, T.: The disjoint shortest paths problem. Discret. Appl. Math. 85(2), 113\u2013138 (1998)","journal-title":"Discret. Appl. Math."},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF01840371","volume":"2","author":"MA Erdmann","year":"1987","unstructured":"Erdmann, M.A., Lozano-P\u00e9rez, T.: On multiple moving objects. Algorithmica 2, 477\u2013521 (1987)","journal-title":"Algorithmica"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Gajjar, K., Jha, A.V., Kumar, M., Lahiri, A.: Reconfiguring shortest paths in graphs. In: AAAI, pp. 9758\u20139766. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i9.21211"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Guo, L., Deng, Y., Liao, K., He, Q., Sellis, T., Hu, Z.: A fast algorithm for optimally finding partially disjoint shortest paths. In: 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), pp. 1456\u20131462 (2018)","DOI":"10.24963\/ijcai.2018\/202"},{"issue":"3\u20134","key":"17_CR13","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s004539910025","volume":"26","author":"D Halperin","year":"2000","unstructured":"Halperin, D., Latombe, J., Wilson, R.H.: A general framework for assembly planning: the motion space approach. Algorithmica 26(3\u20134), 577\u2013601 (2000)","journal-title":"Algorithmica"},{"issue":"3","key":"17_CR14","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1137\/0215055","volume":"15","author":"JE Hopcroft","year":"1986","unstructured":"Hopcroft, J.E., Wilfong, G.T.: Reducing multiple object motion planning to graph searching. SIAM J. Comput. 15(3), 768\u2013785 (1986)","journal-title":"SIAM J. Comput."},{"key":"17_CR15","unstructured":"Jennings, J., Whelan, G., Evans, W.: Cooperative search and rescue with a team of mobile robots. In: 8th International Conference on Advanced Robotics (ICAR\u201997), pp. 193\u2013200 (1997)"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Lochet, W.: A polynomial time algorithm for the $$k$$-disjoint shortest paths problem. In: ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 169\u2013178. SIAM (2021)","DOI":"10.1137\/1.9781611976465.12"},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Mataric, M.J., Nilsson, M., Simsarin, K.T.: Cooperative multi-robot box-pushing. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS 1995), pp. 556\u2013561 (1995)","DOI":"10.1109\/IROS.1995.525940"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Raghavan, P., Sudan, M., Tamaki, H.: Motion planning on a graph (extended abstract). In: 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 511\u2013520. IEEE Computer Society (1994)","DOI":"10.1109\/SFCS.1994.365740"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Robertson, N., Seymour, P.D.: Graph minors .xiii. the disjoint paths problem. J. Comb. Theory, Ser. B 63(1), 65\u2013110 (1995)","DOI":"10.1006\/jctb.1995.1006"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Rodr\u00edguez, S., Amato, N.M.: Behavior-based evacuation planning. In: IEEE International Conference on Robotics and Automation (ICRA 2010), pp. 350\u2013355 (2010)","DOI":"10.1109\/ROBOT.2010.5509502"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Rus, D., Donald, B.R., Jennings, J.: Moving furniture with teams of autonomous robots. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS 1995), pp. 235\u2013242 (1995)","DOI":"10.1109\/IROS.1995.525802"},{"issue":"3","key":"17_CR22","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1016\/j.ejor.2009.06.017","volume":"202","author":"A Sede\u00f1o-Noda","year":"2010","unstructured":"Sede\u00f1o-Noda, A., Gonz\u00e1lez-Mart\u00edn, C.: On the K shortest path trees problem. Eur. J. Oper. Res. 202(3), 628\u2013635 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Smith, B.S., Egerstedt, M., Howard, A.M.: Automatic deployment and formation control of decentralized multi-agent networks. In: IEEE International Conference on Robotics and Automation (ICRA 2008), pp. 134\u2013139 (2008)","DOI":"10.1109\/ROBOT.2008.4543198"},{"issue":"11","key":"17_CR24","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1287\/mnsc.17.11.712","volume":"17","author":"JY Yen","year":"1971","unstructured":"Yen, J.Y.: Finding the $$k$$ shortest loopless paths in a network. Manage. Sci. 17(11), 712\u2013716 (1971)","journal-title":"Manage. Sci."}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-74498-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T22:03:36Z","timestamp":1735596216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-74498-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,20]]},"ISBN":["9783031744976","9783031744983"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-74498-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,10,20]]},"assertion":[{"value":"20 October 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nagoya","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sss2024.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}