Complexity of the virtual network embedding with uniform demands

DOI10.1007/S10479-026-07088-YMaRDI QIDQ6835242zbMATH OpenFDO

Authors Amal Benhamiche, Pierre Fouilhoux, L. Létocart, Nancy Perrot, Alexis Schneider

Publication date 30 March 2026

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10479-026-07088-Y

zbMATH Keywords

complexitydynamic programminggraph topologiespolynomial casesvirtual network embedding

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Operations research and management science (90Bxx)

Cites work

• A note on graphs spanned by Eulerian graphs
• A polynomial algorithm for the min-cut linear arrangement of trees
• Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut
• Design of Survivable Networks: A survey
• Finding Large Clique Minors is Hard
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Min Cut is NP-complete for edge weighted trees
• On the computational complexity of the virtual network embedding problem
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Topology of series-parallel networks
• Wireless mesh networks: a survey

This page was built for publication: Complexity of the virtual network embedding with uniform demands

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6835242)