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
TypeArticle accepté pour publication ou publié
Journal nameJournal of Combinatorial Optimization
Kluwer Academic Publishers
MetadataShow full item record
Abstract (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 / Keywordsfacet; series-parallel graph; k-edge connected subgraph; polytope
Showing items related by title and author.
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié