Abstract (EN)

Given G = (V;E) an undirected graph and a nonnegative cost function c : E → ℚ, the 2-edge connected spanning subgraph problem (TECSP for short) is to find a two-edge connected subgraph HP = (V; F) of G with minimum cost (i.e., c(F) = Σe∈F c(e) is minimum). If c(e) > 0 for all e ∈ E then every optimal solution for TECSP is an inclusionwise minimal two-edge connected subgraph. In this paper we provide preliminary results, from a polyhedral point of view, concerning the inclusionwise minimal solutions of TECSP. This problem is clearly NP-Hard. We propose an ILP formulation for the problem and study the associated polytope for the wheels. Morever, we describe some valid inequalities and propose a branch-and-cut algorithm for the problem.