Steiner k-Edge Connected Subgraph Polyhedra

M. Didi Biha () and A.R. Mahjoub ()
Additional contact information
M. Didi Biha: École Polytechnique
A.R. Mahjoub: Université de Clermont II, Complexe Scientifique des Cézeaux

Journal of Combinatorial Optimization, 2000, vol. 4, issue 1, No 7, 144 pages

Abstract: Abstract 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 = 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.

Keywords: k-edge connected subgraph; polytope; series-parallel graph; cut; facet (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1009893108387 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:1:d:10.1023_a:1009893108387

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009893108387

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().