{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:04:41Z","timestamp":1757617481338,"version":"3.44.0"},"publisher-location":"Singapore","reference-count":20,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819610891"},{"type":"electronic","value":"9789819610907"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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-981-96-1090-7_2","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:32:31Z","timestamp":1741105951000},"page":"16-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Optimal Absolute Approximation Algorithm for\u00a0Computing k Restricted Shortest Paths"],"prefix":"10.1007","author":[{"given":"Yue","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"2_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Upper Saddle River (1995)"},{"key":"2_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.: Graph Theory. Springer, Cham (2008). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"key":"2_CR3","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s10878-015-9934-2","volume":"32","author":"L Guo","year":"2016","unstructured":"Guo, L.: Efficient approximation algorithms for computing $$k$$ disjoint constrained shortest paths. J. Comb. Optim. 32, 144\u2013158 (2016)","journal-title":"J. Comb. Optim."},{"key":"2_CR4","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: Proceedings of IJCAI 2018, pp. 1456\u20131462 (2018)","DOI":"10.24963\/ijcai.2018\/202"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Guo, L., Liao, K., Shen, H., Li, P.: Efficient approximation algorithms for computing $$k$$ disjoint restricted shortest paths. In: Proceedings of SPAA 2015, pp. 62\u201364 (2015)","DOI":"10.1145\/2755573.2755608"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Guo, L., Shen, H., Liao, K.: Improved approximation algorithms for computing $$k$$ disjoint paths subject to two constraints. In: Proceedings of COCOON 2013, pp. 325\u2013336 (2013)","DOI":"10.1007\/978-3-642-38768-5_30"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/net.3230100403","volume":"10","author":"GY Handler","year":"1980","unstructured":"Handler, G.Y., Zang, I.: A dual algorithm for the constrained shortest path problem. Networks 10, 293\u2013309 (1980)","journal-title":"Networks"},{"key":"2_CR8","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, 36\u201342 (1992)","journal-title":"Math. Oper. Res."},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"2_CR10","unstructured":"Johnson, D.S., Garey, M.R.: Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman, New York (1979)"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Mari, M., Mukherjee, A., Pilipczuk, M., Sankowski, P.: Shortest disjoint paths on a grid. In: Proceedings of SODA 2024, pp. 346\u2013365 (2024)","DOI":"10.1137\/1.9781611977912.14"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1109\/MIC.2002.1067740","volume":"6","author":"DA Menasce","year":"2002","unstructured":"Menasce, D.A.: QoS issues in web services. IEEE Internet Comput. 6, 72\u201375 (2002)","journal-title":"IEEE Internet Comput."},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Misra, S., Xue, G., Yang, D.: Polynomial time approximations for multi-path routing with bandwidth and delay constraints. In: Proceedings of INFOCOM 2009, pp. 558\u2013566 (2009)","DOI":"10.1109\/INFCOM.2009.5061962"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Orda, A., Sprintson, A.: Efficient algorithms for computing disjoint QoS paths. In: Proceedings of INFOCOM 2004, pp. 727\u2013738 (2004)","DOI":"10.1109\/INFCOM.2004.1354543"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1093\/ietisy\/e90-d.2.465","volume":"90","author":"C Peng","year":"2007","unstructured":"Peng, C., Shen, H.: A new approximation algorithm for computing $$2$$-restricted disjoint paths. IEICE Trans. Inf. Syst. 90, 465\u2013472 (2007)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"2_CR16","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"key":"2_CR17","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, 125\u2013145 (1974)","journal-title":"Networks"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"2598","DOI":"10.1109\/TNSM.2023.3237832","volume":"20","author":"B Tao","year":"2023","unstructured":"Tao, B., Xiao, M., Zhao, J.: Minimum-weight link-disjoint paths with a bounded number of shared nodes. IEEE Trans. Netw. Serv. Manage. 20, 2598\u20132610 (2023)","journal-title":"IEEE Trans. Netw. Serv. Manage."},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1109\/TNET.2007.900712","volume":"16","author":"G Xue","year":"2008","unstructured":"Xue, G., Zhang, W., Tang, J., Thulasiraman, K.: Polynomial time approximation algorithms for multi-constrained QoS routing. IEEE\/ACM Trans. Networking 16, 656\u2013669 (2008)","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1109\/TNET.2018.2823912","volume":"26","author":"J Yallouz","year":"2018","unstructured":"Yallouz, J., Rottenstreich, O., Babarczi, P., Mendelson, A., Orda, A.: Minimum-weight link-disjoint node-\u201csomewhat disjoint\u2019\u2019 paths. IEEE\/ACM Trans. Networking 26, 1110\u20131122 (2018)","journal-title":"IEEE\/ACM Trans. Networking"}],"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-981-96-1090-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T06:53:32Z","timestamp":1757141612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","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":"Shanghai","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":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}