Thumbnail - Request a copy

Steiner 2-edge connected subgraph polytopes on series-parallel graphs

Baïou, Mourad; Mahjoub, Ali Ridha (1997), Steiner 2-edge connected subgraph polytopes on series-parallel graphs, SIAM Journal on Discrete Mathematics, 10, 3, p. 505-514. http://dx.doi.org/10.1137/S0895480193259813

Type
Article accepté pour publication ou publié
Date
1997
Journal name
SIAM Journal on Discrete Mathematics
Volume
10
Number
3
Publisher
SIAM
Pages
505-514
Publication identifier
Metadata
Show full item record
Author(s)
Baïou, Mourad
Mahjoub, Ali Ridha
Abstract (EN)
Given a graph G=(V,E) with weights on its edges and a set of specified nodes $S\subseteq V$, the Steiner 2-edge survivable network problem is to find a minimum weight subgraph of G such that between every two nodes of S there are at least two edge-disjoint paths. This problem has applications to the design of reliable communication and transportation networks. In this paper, we give a complete linear description of the polytope associated with the solutions to this problem when the underlying graph is series-parallel. We also discuss related polyhedra.
Subjects / Keywords
Series-parallel graphs; Connected subgraphs; Polytopes