{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T16:54:53Z","timestamp":1773680093432,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T00:00:00Z","timestamp":1771372800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T00:00:00Z","timestamp":1771372800000},"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":["Ann Oper Res"],"published-print":{"date-parts":[[2026,3]]},"DOI":"10.1007\/s10479-026-07088-y","type":"journal-article","created":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T20:51:24Z","timestamp":1771447884000},"page":"1141-1167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of the virtual network embedding with uniform demands"],"prefix":"10.1007","volume":"358","author":[{"given":"Amal","family":"Benhamiche","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4746-5783","authenticated-orcid":false,"given":"Pierre","family":"Fouilhoux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucas","family":"L\u00e9tocart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nancy","family":"Perrot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexis","family":"Schneider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,18]]},"reference":[{"key":"7088_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2024.110900","volume":"256","author":"B Addis","year":"2025","unstructured":"Addis, B., Boumerdassi, S., Riggio, R., et al. (2025). Function placement for in-network federated learning. Computer Networks, 256, Article 110900.","journal-title":"Computer Networks"},{"key":"7088_CR2","doi-asserted-by":"publisher","unstructured":"Ahuja, R.K., Magnanti, T.L., & Orlin, J.B. (1988) Network flows. Cambridge, Mass.: Alfred P. Sloan School of Management, Massachusetts, https:\/\/doi.org\/10.21236\/ada594171","DOI":"10.21236\/ada594171"},{"issue":"4","key":"7088_CR3","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/j.comnet.2004.12.001","volume":"47","author":"IF Akyildiz","year":"2005","unstructured":"Akyildiz, I. F., Wang, X., & Wang, W. (2005). Wireless mesh networks: a survey. Computer networks, 47(4), 445\u2013487.","journal-title":"Computer networks"},{"key":"7088_CR4","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.endm.2016.03.028","volume":"52","author":"E Amaldi","year":"2016","unstructured":"Amaldi, E., Coniglio, S., Koster, A. M., et al. (2016). On the computational complexity of the virtual network embedding problem. Electronic Notes in Discrete Mathematics, 52, 213\u2013220. https:\/\/doi.org\/10.1016\/j.endm.2016.03.028","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"4","key":"7088_CR5","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/MC.2005.136","volume":"38","author":"T Anderson","year":"2005","unstructured":"Anderson, T., Peterson, L., Shenker, S., et al. (2005). Overcoming the internet impasse through virtualization. Computer, 38(4), 34\u201341. https:\/\/doi.org\/10.1109\/MC.2005.136","journal-title":"Computer"},{"key":"7088_CR6","doi-asserted-by":"publisher","unstructured":"Ballani, H., Costa, P., Karagiannis, T., et\u00a0al. (2011) Towards predictable datacenter networks. In: Proceedings of the ACM SIGCOMM 2011 Conference, pp 242\u2013253, https:\/\/doi.org\/10.1145\/2018436.2018465","DOI":"10.1145\/2018436.2018465"},{"key":"7088_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2019.100555","volume":"35","author":"A Benhamiche","year":"2020","unstructured":"Benhamiche, A., Mahjoub, A. R., Perrot, N., et al. (2020). Capacitated multi-layer network design with unsplittable demands: Polyhedra and branch-and-cut. Discrete Optimization, 35, Article 100555. https:\/\/doi.org\/10.1016\/j.disopt.2019.100555","journal-title":"Discrete Optimization"},{"key":"7088_CR8","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF02110141","volume":"3","author":"S Cosares","year":"1994","unstructured":"Cosares, S., & Saniee, I. (1994). An optimization problem related to balancing loads on sonet rings. Telecommunication Systems, 3, 165\u2013181. https:\/\/doi.org\/10.1007\/BF02110141","journal-title":"Telecommunication Systems"},{"key":"7088_CR9","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2010) Graph theory (vol. 173)","DOI":"10.1007\/978-3-642-14279-6"},{"issue":"2","key":"7088_CR10","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R. J. (1965). Topology of series-parallel networks. J. Math. Anal. Appl., 10(2), 303\u2013318.","journal-title":"J. Math. Anal. Appl."},{"issue":"2","key":"7088_CR11","doi-asserted-by":"publisher","first-page":"197","DOI":"10.7155\/jgaa.00183","volume":"13","author":"D Eppstein","year":"2009","unstructured":"Eppstein, D. (2009). Finding large clique minors is hard. J. Graph Algorithms Appl, 13(2), 197\u2013204. https:\/\/doi.org\/10.7155\/jgaa.00183","journal-title":"J. Graph Algorithms Appl"},{"key":"7088_CR12","doi-asserted-by":"publisher","unstructured":"Figiel, A., Kellerhals, L., Niedermeier, R., et\u00a0al. (2021) Optimal virtual network embeddings for tree topologies. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pp 221\u2013231, https:\/\/doi.org\/10.1145\/3409964.3461787","DOI":"10.1145\/3409964.3461787"},{"issue":"4","key":"7088_CR13","doi-asserted-by":"publisher","first-page":"1888","DOI":"10.1109\/surv.2013.013013.00155","volume":"15","author":"A Fischer","year":"2013","unstructured":"Fischer, A., Botero, J. F., Beck, M. T., et al. (2013). Virtual network embedding: A survey. IEEE Communications Surveys & Tutorials, 15(4), 1888\u20131906. https:\/\/doi.org\/10.1109\/surv.2013.013013.00155","journal-title":"IEEE Communications Surveys & Tutorials"},{"key":"7088_CR14","doi-asserted-by":"publisher","unstructured":"Garey, Johnson, & Stockmeyer (1974) Some simplfied np-hard problems. STOC \u201974: Proceedings of the sixth annual ACM symposium on Theory of computing https:\/\/doi.org\/10.1145\/800119.803884","DOI":"10.1145\/800119.803884"},{"key":"7088_CR15","doi-asserted-by":"publisher","DOI":"10.1137\/1024022","volume-title":"Computer and Intractability: A guide to the theory of NP-completness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computer and Intractability: A guide to the theory of NP-completness. W. H: Freeman and Company. https:\/\/doi.org\/10.1137\/1024022"},{"issue":"1","key":"7088_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4615-4669-6_2","volume":"46","author":"H Kerivin","year":"2005","unstructured":"Kerivin, H., & Mahjoub, A. R. (2005). Design of survivable networks. A survey. Networks: An International Journal, 46(1), 1\u201321. https:\/\/doi.org\/10.1007\/978-1-4615-4669-6_2","journal-title":"A survey. Networks: An International Journal"},{"issue":"1\u20133","key":"7088_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-x","volume":"58","author":"B Monien","year":"1988","unstructured":"Monien, B., & Sudborough, I. H. (1988). Min cut is np-complete for edge weighted trees. Theoretical Computer Science, 58(1\u20133), 209\u2013229. https:\/\/doi.org\/10.1016\/0304-3975(88)90028-x","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"7088_CR18","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/s0166-218x(01)00223-2","volume":"115","author":"T Nishizeki","year":"2001","unstructured":"Nishizeki, T., Vygen, J., & Zhou, X. (2001). The edge-disjoint paths problem is np-complete for series-parallel graphs. Discrete Applied Mathematics, 115(1\u20133), 177\u2013186. https:\/\/doi.org\/10.1016\/s0166-218x(01)00223-2","journal-title":"Discrete Applied Mathematics"},{"key":"7088_CR19","unstructured":"Pankratov, S., Aksenov, V., & Schmid, S. (2023) On the complexity of the virtual network embedding in specific tree topologies. arXiv preprint arXiv:2311.05474"},{"issue":"3","key":"7088_CR20","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/jgt.3190030316","volume":"3","author":"WR Pulleyblank","year":"1979","unstructured":"Pulleyblank, W. R. (1979). A note on graphs spanned by eulerian graphs. J. Graph Theory., 3(3), 309\u2013310. https:\/\/doi.org\/10.1002\/jgt.3190030316","journal-title":"J. Graph Theory."},{"issue":"2","key":"7088_CR21","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1109\/tnet.2020.2975646","volume":"28","author":"M Rost","year":"2020","unstructured":"Rost, M., & Schmid, S. (2020). On the hardness and inapproximability of virtual network embeddings. IEEE\/ACM transactions on networking, 28(2), 791\u2013803. https:\/\/doi.org\/10.1109\/tnet.2020.2975646","journal-title":"IEEE\/ACM transactions on networking"},{"issue":"3","key":"7088_CR22","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2805789.2805792","volume":"45","author":"M Rost","year":"2015","unstructured":"Rost, M., Fuerst, C., & Schmid, S. (2015). Beyond the stars: Revisiting virtual cluster embeddings. ACM SIGCOMM Computer Communication Review, 45(3), 12\u201318. https:\/\/doi.org\/10.1145\/2805789.2805792","journal-title":"ACM SIGCOMM Computer Communication Review"},{"issue":"3","key":"7088_CR23","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/mcomstd.001.1900040","volume":"4","author":"CW da Silva","year":"2020","unstructured":"da Silva, C. W., Benhamiche, A., Perrot, N., et al. (2020). Network function mapping: From 3g entities to 5g service-based functions decomposition. IEEE Communications Standards Magazine, 4(3), 46\u201352. https:\/\/doi.org\/10.1109\/mcomstd.001.1900040","journal-title":"IEEE Communications Standards Magazine"},{"key":"7088_CR24","doi-asserted-by":"publisher","unstructured":"Tootaghaj, D.Z., Ahmed, F., Sharma, P., et\u00a0al. (2020) Homa: An efficient topology and route management approach in sd-wan overlays. In: IEEE INFOCOM 2020-IEEE Conference on Computer Communications, IEEE, pp 2351\u20132360, https:\/\/doi.org\/10.1109\/infocom41043.2020.9155503","DOI":"10.1109\/infocom41043.2020.9155503"},{"issue":"3","key":"7088_CR25","doi-asserted-by":"publisher","first-page":"1487","DOI":"10.1109\/tnsm.2020.3002849","volume":"17","author":"H Wu","year":"2020","unstructured":"Wu, H., Zhou, F., Chen, Y., et al. (2020). On virtual network embedding: Paths and cycles. IEEE Transactions on Network and Service Management, 17(3), 1487\u20131500. https:\/\/doi.org\/10.1109\/tnsm.2020.3002849","journal-title":"IEEE Transactions on Network and Service Management"},{"issue":"4","key":"7088_CR26","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M Yannakakis","year":"1985","unstructured":"Yannakakis, M. (1985). A polynomial algorithm for the min-cut linear arrangement of trees. Journal of the ACM (JACM), 32(4), 950\u2013988. https:\/\/doi.org\/10.1145\/4221.4228","journal-title":"Journal of the ACM (JACM)"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07088-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-026-07088-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07088-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T16:06:08Z","timestamp":1773677168000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-026-07088-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,18]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["7088"],"URL":"https:\/\/doi.org\/10.1007\/s10479-026-07088-y","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,18]]},"assertion":[{"value":"22 January 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Amal Benhamiche, Pierre Fouilhoux, Lucas L\u00e9tocart, Nancy Perrot and Alexis Schneider have no conflict of interest to declare about the scientific materials contained in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}]}}