Given a graph representing a substrate (or physical) network with node and edge capacities and a set of virtual networks with node capacity demands and node-tonode traffic demands, the Virtual Network Embedding problem (VNE) calls for an embedding of (a subset of) the virtual networks onto the substrate network which maximizes the total profit while respecting the physical node and edge capacities. In this work, we investigate the computational complexity of VNE. In particular, we present a polynomial-time reduction from the maximum stable set problem which implies strong N P-hardness for VNE even for very special subclasses of graphs and yields a strong inapproximability result for general graphs. We also consider the special cases obtained when fixing one of the dimensions of the problem to one. We show that VNE is still strongly N P-hard when a single virtual network request is present or when each virtual network request consists of a single virtual node and that it is weakly N P-hard for the case with a single physical node.

(2016). On the computational complexity of the virtual network embedding problem . In ELECTRONIC NOTES IN DISCRETE MATHEMATICS. Retrieved from http://hdl.handle.net/10446/229388

On the computational complexity of the virtual network embedding problem

Coniglio, Stefano;
2016-01-01

Abstract

Given a graph representing a substrate (or physical) network with node and edge capacities and a set of virtual networks with node capacity demands and node-tonode traffic demands, the Virtual Network Embedding problem (VNE) calls for an embedding of (a subset of) the virtual networks onto the substrate network which maximizes the total profit while respecting the physical node and edge capacities. In this work, we investigate the computational complexity of VNE. In particular, we present a polynomial-time reduction from the maximum stable set problem which implies strong N P-hardness for VNE even for very special subclasses of graphs and yields a strong inapproximability result for general graphs. We also consider the special cases obtained when fixing one of the dimensions of the problem to one. We show that VNE is still strongly N P-hard when a single virtual network request is present or when each virtual network request consists of a single virtual node and that it is weakly N P-hard for the case with a single physical node.
2016
Amaldi, Edoardo; Coniglio, Stefano; Koster, Arie M. C. A.; Tieves, Martin
File allegato/i alla scheda:
File Dimensione del file Formato  
2015-INOC.pdf

Solo gestori di archivio

Versione: publisher's version - versione editoriale
Licenza: Licenza default Aisberg
Dimensione del file 201.23 kB
Formato Adobe PDF
201.23 kB Adobe PDF   Visualizza/Apri
11311-1023988_Amaldi.pdf

accesso aperto

Versione: postprint - versione referata/accettata senza referaggio
Licenza: Creative commons
Dimensione del file 282.94 kB
Formato Adobe PDF
282.94 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/229388
Citazioni
  • Scopus 120
  • ???jsp.display-item.citation.isi??? ND
social impact