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
TypeArticle accepté pour publication ou publié
Journal nameSIAM Journal on Discrete Mathematics
MetadataShow full item record
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 / KeywordsSeries-parallel graphs; Connected subgraphs; Polytopes
Showing items related by title and author.