6 papers
On the Virtual Network Embedding polytope
Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart +2
We initiate the polyhedral study of the Virtual Network Embedding (VNE) problem, which arises in modern telecommunication networks. We propose new valid inequalities for the so-cal…
A decomposition approach for large virtual network embedding
Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart +2
Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated…
Extended formulations for the maximum weighted co-2-plex problem
Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe +1
Given an input graph and weights on its vertices, the maximum co-2-plex problem is to find a subset of vertices maximizing the sum of their weights and inducing a graph of degree a…
Complexity of the Virtual Network Embedding with uniform demands
Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart +2
We study the complexity of the Virtual Network Embedding Problem (VNE), which is the combinatorial core of several telecommunication problems related to the implementation of virtu…
A generic Branch-and-Cut algorithm for bi-objective binary linear programs
Pierre Fouilhoux, Lucas Létocart, Yue Zhang
This paper presents the first generic bi-objective binary linear branch-and-cut algorithm. Studying the impact of valid inequalities in solution and objective spaces, two cutting f…
Contractions in perfect graph
Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe +1
In this paper, we characterize the class of {\em contraction perfect} graphs which are the graphs that remain perfect after the contraction of any edge set. We prove that a graph i…