Steiner k-edge connected subgraph polyhedra
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2000), Steiner k-edge connected subgraph polyhedra, Journal of Combinatorial Optimization, 4, 1, p. 131-144. http://dx.doi.org/10.1023/A:1009893108387
Type
Article accepté pour publication ou publiéDate
2000Journal name
Journal of Combinatorial OptimizationVolume
4Number
1Publisher
Kluwer Academic Publishers
Pages
131-144
Publication identifier
Metadata
Show full item recordAbstract (EN)
In this paper we consider the Steiner k-edge survivable network problem. We discuss the polytope associated with the solutions to that problem. We show that when the graph is series-parallel and k is even, the polytope is completely described by the trivial constraints and the so called Steiner-cut constraints. This generalizes recent work of Ba¨ ıou and Mahjoub, SIAM J. Discrete Mathematics, vol. 10, pp. 505–514, 1997 for the case k D 2. As a consequence, we obtain in this case a linear description of the polyhedron associated with the problem when multiple copies of an edge are allowed.Subjects / Keywords
facet; series-parallel graph; k-edge connected subgraph; polytopeRelated items
Showing items related by title and author.
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (1996) Article accepté pour publication ou publié
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2004) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Kerivin, Hervé; Mahjoub, Ali Ridha (2001) Article accepté pour publication ou publié