{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:58:23Z","timestamp":1761649103856,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T00:00:00Z","timestamp":1672444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["21K21288","19K11942"],"award-info":[{"award-number":["21K21288","19K11942"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Netw Syst Manage"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10922-022-09715-y","type":"journal-article","created":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T17:02:16Z","timestamp":1672506136000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Speedy and Efficient Service Chaining and Function Placement Based on Lagrangian Heuristics for Capacitated Shortest Path Tour Problem"],"prefix":"10.1007","volume":"31","author":[{"given":"Takanori","family":"Hara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masahiro","family":"Sasabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,31]]},"reference":[{"issue":"2","key":"9715_CR1","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1109\/MCOM.2015.7045396","volume":"53","author":"B Han","year":"2015","unstructured":"Han, B., Gopalakrishnan, V., Ji, L., Lee, S.: Network Function Virtualization: Challenges and Opportunities for Innovations. IEEE Commun. Mag. 53(2), 90\u201397 (2015). https:\/\/doi.org\/10.1109\/MCOM.2015.7045396","journal-title":"IEEE Commun. Mag."},{"key":"9715_CR2","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/j.jnca.2016.09.001","volume":"75","author":"D Bhamare","year":"2016","unstructured":"Bhamare, D., Jain, R., Samaka, M., Erbad, A.: A Survey on Service Function Chaining. J. Netw. Comput. Appl. 75, 138\u2013155 (2016). https:\/\/doi.org\/10.1016\/j.jnca.2016.09.001","journal-title":"J. Netw. Comput. Appl."},{"key":"9715_CR3","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/j.comnet.2018.01.021","volume":"133","author":"B Yi","year":"2018","unstructured":"Yi, B., Wang, X., Li, K., Das, S., Huang, M.: A Comprehensive Survey of Network Function Virtualization. Comput. Netw. 133, 212\u2013262 (2018). https:\/\/doi.org\/10.1016\/j.comnet.2018.01.021","journal-title":"Comput. Netw."},{"issue":"3","key":"9715_CR4","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1109\/TNSM.2016.2598420","volume":"13","author":"JG Herrera","year":"2016","unstructured":"Herrera, J.G., Botero, J.F.: Resource Allocation in NFV: A Comprehensive Survey. IEEE Trans. Netw. Serv. Manage. 13(3), 518\u2013532 (2016). https:\/\/doi.org\/10.1109\/TNSM.2016.2598420","journal-title":"IEEE Trans. Netw. Serv. Manage."},{"key":"9715_CR5","doi-asserted-by":"publisher","unstructured":"Halpern, J., Pignataro, C.: Service Function Chaining (SFC) Architecture. Technical Report RFC7665 (October 2015). https:\/\/doi.org\/10.17487\/RFC7665","DOI":"10.17487\/RFC7665"},{"key":"9715_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: Proc. of STOC. ACM,, vol. 42, pp. 160\u2013177 (2005)","DOI":"10.1137\/070702370"},{"key":"9715_CR7","doi-asserted-by":"crossref","unstructured":"Bhat, S., Rouskas, G.N.: Service-Concatenation Routing with Applications to Network Functions Virtualization. In: Proc. of 26th International Conference on Computer Communication and Networks (ICCCN), pp. 1\u20139 (2017)","DOI":"10.1109\/ICCCN.2017.8038463"},{"key":"9715_CR8","doi-asserted-by":"publisher","unstructured":"Gao, L., Rouskas, G.N.: Congestion Minimization for Service Chain Routing Problems With Path Length Considerations. IEEE\/ACM Transactions on Networking, 1\u201314 (2020). https:\/\/doi.org\/10.1109\/TNET.2020.3017792","DOI":"10.1109\/TNET.2020.3017792"},{"issue":"1","key":"9715_CR9","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1109\/TNSM.2020.3044329","volume":"18","author":"M Sasabe","year":"2021","unstructured":"Sasabe, M., Hara, T.: Capacitated Shortest Path Tour Problem Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks. IEEE Trans. Netw. Serv. Manage. 18(1), 104\u2013117 (2021). https:\/\/doi.org\/10.1109\/TNSM.2020.3044329","journal-title":"IEEE Trans. Netw. Serv. Manage."},{"issue":"1","key":"9715_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s11590-010-0258-y","volume":"6","author":"P Festa","year":"2012","unstructured":"Festa, P.: Complexity Analysis and Optimization of the Shortest Path Tour Problem. Optimization Letters 6(1), 163\u2013175 (2012)","journal-title":"Optimization Letters"},{"issue":"3","key":"9715_CR11","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/j.ejor.2013.04.029","volume":"230","author":"P Festa","year":"2013","unstructured":"Festa, P., Guerriero, F., Lagan\u00e0, D., Musmanno, R.: Solving the Shortest Path Tour Problem. Eur. J. Oper. Res. 230(3), 464\u2013474 (2013)","journal-title":"Eur. J. Oper. Res."},{"key":"9715_CR12","unstructured":"Festa, P.: The Shortest Path Tour Problem: Problem Definition, Modeling, and Optimization. In: Proc. of INOC, pp. 1\u20137 (2009)"},{"key":"9715_CR13","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.cor.2016.04.002","volume":"74","author":"D Ferone","year":"2016","unstructured":"Ferone, D., Festa, P., Guerriero, F., Lagan\u00e0, D.: The Constrained Shortest Path Tour Problem. Computers & Operations Research 74, 64\u201377 (2016). https:\/\/doi.org\/10.1016\/j.cor.2016.04.002","journal-title":"Computers & Operations Research"},{"key":"9715_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.endm.2018.07.019","volume":"69","author":"RC de Andrade","year":"2018","unstructured":"de Andrade, R.C., Saraiva, R.D.: An Integer Linear Programming Model for the Constrained Shortest Path Tour Problem. Electronic Notes in Discrete Mathematics 69, 141\u2013148 (2018)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"1","key":"9715_CR15","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1111\/itor.12782","volume":"28","author":"RD Saraiva","year":"2021","unstructured":"Saraiva, R.D., de Andrade, R.C.: Constrained Shortest Path Tour Problem: Models, Valid Inequalities, and Lagrangian Heuristics. Int. Trans. Oper. Res. 28(1), 222\u2013261 (2021). https:\/\/doi.org\/10.1111\/itor.12782","journal-title":"Int. Trans. Oper. Res."},{"key":"9715_CR16","doi-asserted-by":"publisher","unstructured":"Sallam, G., Gupta, G.R., Li, B., Ji, B.: Shortest Path and Maximum Flow Problems Under Service Function Chaining Constraints. In: Proc. of IEEE Conference on Computer Communications, pp. 2132\u20132140 (2018). https:\/\/doi.org\/10.1109\/INFOCOM.2018.8485996","DOI":"10.1109\/INFOCOM.2018.8485996"},{"key":"9715_CR17","doi-asserted-by":"publisher","first-page":"165399","DOI":"10.1109\/ACCESS.2019.2934725","volume":"7","author":"N Hyodo","year":"2019","unstructured":"Hyodo, N., Sato, T., Shinkuma, R., Oki, E.: Virtual Network Function Placement for Service Chaining by Relaxing Visit Order and Non-Loop Constraints. IEEE Access 7, 165399\u2013165410 (2019)","journal-title":"IEEE Access"},{"key":"9715_CR18","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.future.2018.09.037","volume":"91","author":"G Sun","year":"2019","unstructured":"Sun, G., Li, Y., Yu, H., Vasilakos, A.V., Du, X., Guizani, M.: Energy-Efficient and Traffic-Aware Service Function Chaining Orchestration in Multi-Domain Networks. Futur. Gener. Comput. Syst. 91, 347\u2013360 (2019). https:\/\/doi.org\/10.1016\/j.future.2018.09.037","journal-title":"Futur. Gener. Comput. Syst."},{"issue":"3","key":"9715_CR19","doi-asserted-by":"publisher","first-page":"1320","DOI":"10.1109\/TNET.2018.2833815","volume":"26","author":"N Huin","year":"2018","unstructured":"Huin, N., Jaumard, B., Giroire, F.: Optimal Network Service Chain Provisioning. IEEE\/ACM Trans. Networking 26(3), 1320\u20131333 (2018). https:\/\/doi.org\/10.1109\/TNET.2018.2833815","journal-title":"IEEE\/ACM Trans. Networking"},{"issue":"3","key":"9715_CR20","doi-asserted-by":"publisher","first-page":"1192","DOI":"10.1109\/TNET.2019.2912717","volume":"27","author":"T Nguyen","year":"2019","unstructured":"Nguyen, T., Girard, A., Rosenberg, C., Fdida, S.: Routing via Functions in Virtual Networks: The Curse of Choices. IEEE\/ACM Trans. Networking 27(3), 1192\u20131205 (2019). https:\/\/doi.org\/10.1109\/TNET.2019.2912717","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"9715_CR21","doi-asserted-by":"crossref","unstructured":"Hara, T., Sasabe, M.: Lagrangian Heuristics for Capacitated Shortest Path Tour Problem Based Online Service Chaining. In: Proc. of 2022 IEEE\/IFIP Network Operations and Management Symposium, pp. 1\u20139 (2022)","DOI":"10.1109\/NOMS54207.2022.9789758"},{"key":"9715_CR22","unstructured":"ILOG: IBM ILOG CPLEX Optimizer. https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio. Accessed 15 Jun. 2022 (2020)"},{"key":"9715_CR23","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming, Reprinted Wiley, Chichester (2000)","edition":"Reprinted"},{"key":"9715_CR24","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.comnet.2019.01.036","volume":"152","author":"D Li","year":"2019","unstructured":"Li, D., Hong, P., Xue, K., Pei, J.: Virtual Network Function Placement and Resource Optimization in NFV and Edge Computing Enabled Networks. Comput. Netw. 152, 12\u201324 (2019). https:\/\/doi.org\/10.1016\/j.comnet.2019.01.036","journal-title":"Comput. Netw."},{"key":"9715_CR25","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.comnet.2019.01.041","volume":"158","author":"O Soualah","year":"2019","unstructured":"Soualah, O., Mechtri, M., Ghribi, C., Zeghlache, D.: Online and Batch Algorithms for VNFs Placement and Chaining. Comput. Netw. 158, 98\u2013113 (2019). https:\/\/doi.org\/10.1016\/j.comnet.2019.01.041","journal-title":"Comput. Netw."},{"key":"9715_CR26","doi-asserted-by":"publisher","unstructured":"Alleg, A., Ahmed, T., Mosbah, M., Riggio, R., Boutaba, R.: Delay-aware VNF placement and chaining based on a flexible resource allocation approach. In: Proc. of International Conference on Network and Service Management (CNSM), pp. 1\u20137 (2017). https:\/\/doi.org\/10.23919\/CNSM.2017.8255993","DOI":"10.23919\/CNSM.2017.8255993"},{"key":"9715_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.comcom.2017.02.011","volume":"102","author":"D Bhamare","year":"2017","unstructured":"Bhamare, D., Samaka, M., Erbad, A., Jain, R., Gupta, L., Chan, H.A.: Optimal Virtual Network Function Placement in Multi-Cloud Service Function Chaining Architecture. Comput. Commun. 102, 1\u201316 (2017). https:\/\/doi.org\/10.1016\/j.comcom.2017.02.011","journal-title":"Comput. Commun."},{"issue":"2","key":"9715_CR28","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1109\/TNSM.2018.2815986","volume":"15","author":"M Dieye","year":"2018","unstructured":"Dieye, M., Ahvar, S., Sahoo, J., Ahvar, E., Glitho, R., Elbiaze, H., Crespi, N.: CPVNF: Cost-Efficient Proactive VNF Placement and Chaining for Value-Added Services in Content Delivery Networks. IEEE Trans. Netw. Serv. Manage. 15(2), 774\u2013786 (2018). https:\/\/doi.org\/10.1109\/TNSM.2018.2815986","journal-title":"IEEE Trans. Netw. Serv. Manage."},{"key":"9715_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.osn.2020.100554","volume":"36","author":"N Kiji","year":"2020","unstructured":"Kiji, N., Sato, T., Shinkuma, R., Oki, E.: Virtual Network Function Placement and Routing for Multicast Service Chaining Using Merged Paths. Opt. Switch. Netw. 36, 1\u201310 (2020). https:\/\/doi.org\/10.1016\/j.osn.2020.100554","journal-title":"Opt. Switch. Netw."},{"issue":"6","key":"9715_CR30","doi-asserted-by":"publisher","first-page":"1060","DOI":"10.1109\/TC.2013.31","volume":"62","author":"C Papagianni","year":"2013","unstructured":"Papagianni, C., Leivadeas, A., Papavassiliou, S., Maglaris, V., Cervell\u00f3-Pastor, C., Monje, \u00c1.: On the Optimal Allocation of Virtual Resources in Cloud Computing Networks. IEEE Trans. Comput. 62(6), 1060\u20131071 (2013). https:\/\/doi.org\/10.1109\/TC.2013.31","journal-title":"IEEE Trans. Comput."},{"key":"9715_CR31","unstructured":"Open MPI: Open Source High Performance Computing. https:\/\/www.open-mpi.org\/. Accessed 15 Jun. 2022 (2020)"},{"key":"9715_CR32","doi-asserted-by":"publisher","unstructured":"Savi, M., Tornatore, M., Verticale, G.: Impact of Processing-Resource Sharing on the Placement of Chained Virtual Network Functions. IEEE Transactions on Cloud Computing, 1\u201314 (2019). https:\/\/doi.org\/10.1109\/TCC.2019.2914387","DOI":"10.1109\/TCC.2019.2914387"},{"issue":"9","key":"9715_CR33","doi-asserted-by":"publisher","first-page":"1765","DOI":"10.1109\/JSAC.2011.111002","volume":"29","author":"S Knight","year":"2011","unstructured":"Knight, S., Nguyen, H.X., Falkner, N., Bowden, R., Roughan, M.: The Internet Topology Zoo. IEEE J. Sel. Areas Commun. 29(9), 1765\u20131775 (2011). https:\/\/doi.org\/10.1109\/JSAC.2011.111002","journal-title":"IEEE J. Sel. Areas Commun."},{"issue":"3","key":"9715_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1103\/PhysRevE.71.036113","volume":"71","author":"V Batagelj","year":"2005","unstructured":"Batagelj, V., Brandes, U.: Efficient Generation of Large Random Networks. Phys. Rev. E 71(3), 1\u20135 (2005). https:\/\/doi.org\/10.1103\/PhysRevE.71.036113","journal-title":"Phys. Rev. E"},{"issue":"10","key":"9715_CR35","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1109\/TC.1985.6312192","volume":"C\u201334","author":"CE Leiserson","year":"1985","unstructured":"Leiserson, C.E.: Fat-trees: Universal Networks for Hardware-efficient Supercomputing. IEEE Trans. Comput. C\u201334(10), 892\u2013901 (1985). https:\/\/doi.org\/10.1109\/TC.1985.6312192","journal-title":"IEEE Trans. Comput."},{"key":"9715_CR36","unstructured":"Boost: Boost Graph Library. https:\/\/www.boost.org\/. Accessed 15 Jun. 2022 (2020)"}],"container-title":["Journal of Network and Systems Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10922-022-09715-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10922-022-09715-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10922-022-09715-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T02:15:43Z","timestamp":1675304143000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10922-022-09715-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,31]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["9715"],"URL":"https:\/\/doi.org\/10.1007\/s10922-022-09715-y","relation":{},"ISSN":["1064-7570","1573-7705"],"issn-type":[{"type":"print","value":"1064-7570"},{"type":"electronic","value":"1573-7705"}],"subject":[],"published":{"date-parts":[[2022,12,31]]},"assertion":[{"value":"22 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 December 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"24"}}