Steiner k-edge connected subgraph polyhedra

Didi Biha, Mohamed; Mahjoub, Ali Ridha

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

2000

Journal name

Journal of Combinatorial Optimization

Volume

Number

Publisher

Kluwer Academic Publishers

Pages

131-144

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 / Keywords

facet; series-parallel graph; k-edge connected subgraph; polytope