On the Polytope of the (1,2)-Survivable Network Design Problem
Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008), On the Polytope of the (1,2)-Survivable Network Design Problem, SIAM Journal on Discrete Mathematics, 22, 4, p. 1640- 1666. http://dx.doi.org/10.1137/050639600
Type
Article accepté pour publication ou publiéDate
2008Journal name
SIAM Journal on Discrete MathematicsVolume
22Number
4Publisher
Society for Industrial and Applied Mathematics
Pages
1640- 1666
Publication identifier
Metadata
Show full item recordAbstract (EN)
This 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.Subjects / Keywords
cut and partition inequalities; polytope; series-parallel graphsRelated items
Showing items related by title and author.
-
Kerivin, Hervé; Mahjoub, Ali Ridha (2002) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Kerivin, Hervé; Mahjoub, Ali Ridha (1998) Communication / Conférence
-
Kerivin, Hervé; Mahjoub, Ali Ridha (2005) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Kerivin, Hervé; Mahjoub, Ali Ridha (2001) Article accepté pour publication ou publié
-
Kerivin, Hervé; Mahjoub, Ali Ridha; Nocq, Charles (2004) Chapitre d'ouvrage