Abstract (EN)

Given an undirected network G=(V,E), a vector of nonnegative integers r=(r(v):v E v) associated with the nodes of G and weights on the edges of G, the survivable network design problem is to determine a minimum-weight subnetwork of G such that between every two nodes u, v of V, there are at least min{r(u),r(v)} edge-disjoint paths. In this paper we study the polytope associated with the solutions to that problem. We show that when the underlying network is series–parallel and r(v) is even for all v E v, the polytope is completely described by the trivial constraints and the so-called cut constraints. As a consequence, we obtain a polynomial time algorithm for the survivable network design problem in that class of networks. This generalizes and unifies known results in the literature. We also obtain a linear description of the polyhedron associated with the problem in the same class of networks when the use of more than one copy of an edge is allowed.