Show simple item record

dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorKerivin, Hervé
dc.contributor.authorDidi Biha, Mohamed
dc.date.accessioned2010-01-09T14:59:50Z
dc.date.available2010-01-09T14:59:50Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2847
dc.language.isoenen
dc.subjectcut and partition inequalitiesen
dc.subjectpolytopeen
dc.subjectseries-parallel graphsen
dc.subject.ddc511en
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.isversionofjnlvol22en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2008
dc.relation.isversionofjnlpages1640- 1666en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/050639600en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSociety for Industrial and Applied Mathematicsen
dc.subject.ddclabelPrincipes généraux des mathématiquesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record