Show simple item record

dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorKerivin, Hervé
dc.contributor.authorDidi Biha, Mohamed
dc.subjectcut and partition inequalitiesen
dc.subjectseries-parallel graphsen
dc.titleOn the Polytope of the (1,2)-Survivable Network Design Problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper deals with the survivable network design problem where each node $v$ has a connectivity type $r(v)$ equal to 1 or 2, and the survivability conditions require the existence of at least $\min\{r(s),r(t)\}$ edge-disjoint paths for all distinct nodes $s$ and $t$. We consider the polytope given by the trivial and cut inequalities together with the partition inequalities. More precisely, we study some structural properties of this polytope which leads us to give some sufficient conditions for this polytope to be integer in the class of series-parallel graphs. With both separation problems for the cut and partition inequalities being polynomially solvable, we then obtain a polynomial time algorithm for the (1,2)-survivable network design problem in a subclass of series-parallel graphs including the outerplanar graph class. We also introduce a new class of facet-defining inequalities for the polytope associated to the (1,2)-survivable network design problem.en
dc.relation.isversionofjnlnameSIAM Journal on Discrete Mathematics
dc.relation.isversionofjnlpages1640- 1666en
dc.relation.isversionofjnlpublisherSociety for Industrial and Applied Mathematicsen
dc.subject.ddclabelPrincipes généraux des mathématiquesen

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record