{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T12:40:10Z","timestamp":1751719210122,"version":"3.41.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319947754"},{"type":"electronic","value":"9783319947761"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94776-1_2","type":"book-chapter","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T01:48:06Z","timestamp":1530236886000},"page":"14-25","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Exact Algorithms for Finding Partial Edge-Disjoint Paths"],"prefix":"10.1007","author":[{"given":"Yunyun","family":"Deng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peihuang","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"issue":"4","key":"2_CR1","doi-asserted-by":"publisher","first-page":"1490","DOI":"10.1137\/130910464","volume":"45","author":"J Chuzhoy","year":"2016","unstructured":"Chuzhoy, J.: Routing in undirected graphs with constant congestion. SIAM J. Comput. 45(4), 1490\u20131532 (2016)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"2_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/2893472","volume":"63","author":"J Chuzhoy","year":"2016","unstructured":"Chuzhoy, J., Li, S.: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. J. ACM (JACM) 63(5), 45 (2016)","journal-title":"J. ACM (JACM)"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-540-72870-2_13","volume-title":"Algorithmic Aspects in Information and Management","author":"R Fleischer","year":"2007","unstructured":"Fleischer, R., Ge, Q., Li, J., Zhu, H.: Efficient algorithms for k-disjoint paths problems on DAGs. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 134\u2013143. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72870-2_13"},{"key":"2_CR4","volume-title":"Computers and Intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. WH Freeman, New York (2002)"},{"key":"2_CR5","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: Accepted by the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence, IJCAI (2018)","DOI":"10.24963\/ijcai.2018\/202"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Guo, L., Liao, K., Shen, H., Li, P.: Brief announcement: efficient approximation algorithms for computing k disjoint restricted shortest paths. In: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 62\u201364. ACM (2015)","DOI":"10.1145\/2755573.2755608"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.tcs.2011.12.009","volume":"432","author":"L Guo","year":"2012","unstructured":"Guo, L., Shen, H.: On the complexity of the edge-disjoint min-min problem in planar digraphs. Theor. Comput. Sci. 432, 58\u201363 (2012)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"2_CR8","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s00453-012-9656-0","volume":"66","author":"L Guo","year":"2013","unstructured":"Guo, L., Shen, H.: On finding min-min disjoint paths. Algorithmica 66(3), 641\u2013653 (2013)","journal-title":"Algorithmica"},{"issue":"1","key":"2_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/moor.17.1.36","volume":"17","author":"R Hassin","year":"1992","unstructured":"Hassin, R.: Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17(1), 36\u201342 (1992)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2_CR10","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0022-247X(66)90020-5","volume":"14","author":"HC Joksch","year":"1966","unstructured":"Joksch, H.C.: The shortest route problem with constraints. J. Math. Anal. App. 14(2), 191\u2013197 (1966)","journal-title":"J. Math. Anal. App."},{"key":"2_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization, vol. 2. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-24488-9"},{"issue":"1","key":"2_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0166-218X(90)90024-7","volume":"26","author":"C-L Li","year":"1990","unstructured":"Li, C.-L., McCormick, S.T., Simchi-Levi, D.: The complexity of finding two disjoint paths with min-max objective function. Discret. Appl. Math. 26(1), 105\u2013115 (1990)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"2_CR13","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1109\/18.212275","volume":"39","author":"RG Ogier","year":"1993","unstructured":"Ogier, R.G., Rutenburg, V., Shacham, N.: Distributed algorithms for computing shortest pairs of disjoint paths. IEEE Trans. Inf. Theory 39(2), 443\u2013455 (1993)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Orda, A., Sprintson, A.: Efficient algorithms for computing disjoint QOS paths. In: INFOCOM 2004. Twenty-Third AnnualJoint Conference of the IEEE Computer and Communications Societies, vol. 1. IEEE (2004)","DOI":"10.1109\/INFCOM.2004.1354543"},{"issue":"1","key":"2_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/322047.322048","volume":"25","author":"Y Shiloach","year":"1978","unstructured":"Shiloach, Y., Perl, Y.: Finding two disjoint paths between two pairs of vertices in a graph. J. ACM (JACM) 25(1), 1\u20139 (1978)","journal-title":"J. ACM (JACM)"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/115994.115998","volume":"21","author":"D Sidhu","year":"1991","unstructured":"Sidhu, D., Nair, R., Abdallah, S.: Finding disjoint paths in networks. ACM SIGCOMM Comput. Commun. Rev. 21, 43\u201351 (1991)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"issue":"2","key":"2_CR17","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1002\/net.3230140209","volume":"14","author":"JW Suurballe","year":"1984","unstructured":"Suurballe, J.W., Tarjan, R.E.: A quick method for finding shortest pairs of disjoint paths. Networks 14(2), 325\u2013336 (1984)","journal-title":"Networks"},{"issue":"2","key":"2_CR18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1002\/net.3230040204","volume":"4","author":"JW Suurballe","year":"1974","unstructured":"Suurballe, J.W.: Disjoint paths in a network. Networks 4(2), 125\u2013145 (1974)","journal-title":"Networks"},{"issue":"6","key":"2_CR19","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.jcss.2010.08.012","volume":"77","author":"BY Wu","year":"2011","unstructured":"Wu, B.Y.: A note on approximating the min-max vertex disjoint paths on directed acyclic graphs. J. Comput. Syst. Sci. 77(6), 1054\u20131057 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2_CR20","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TNET.2005.863451","volume":"14","author":"D Xu","year":"2006","unstructured":"Xu, D., Chen, Y., Xiong, Y., Qiao, C., He, X.: On the complexity of and algorithms for finding the shortest path with a disjoint counterpart. IEEE\/ACM Trans. Netw. (TON) 14(1), 147\u2013158 (2006)","journal-title":"IEEE\/ACM Trans. Netw. (TON)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Yallouz, J., Rottenstreich, O., Babarczi, P., Mendelson, A., Orda, A.: Optimal link-disjoint node-\u201csomewhat disjoint\u201d paths. In: 2016 IEEE 24th International Conference on Network Protocols (ICNP), pp. 1\u201310. IEEE (2016)","DOI":"10.1109\/ICNP.2016.7784451"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94776-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T12:11:33Z","timestamp":1751717493000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94776-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319947754","9783319947761"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94776-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Qing Dao","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 July 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon2018.sdu.edu.cn\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}