Issue |
RAIRO-Oper. Res.
Volume 42, Number 3, July-September 2008
|
|
---|---|---|
Page(s) | 259 - 283 | |
DOI | https://doi.org/10.1051/ro:2008022 | |
Published online | 20 August 2008 |
On the Steiner 2-edge connected subgraph polytope
1
LIMOS, CNRS, Univ. Blaise Pascal, Clermont Ferrand II,
Complexe Sci. des Cézeaux, 63177 Aubière Cedex; present address: LAMSADE, CNRS, Univ. Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France mahjoub@lamsade.dauphine.fr
2
Université Bordeaux 1, IMB, 351, Cours de la Libération,
33 405 Talence Cedex, France; pierre.pesneau@math.u-bordeaux1.fr
Received:
1
December
2005
Accepted:
1
August
2007
In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge connected subgraph problem in that class of graphs.
Mathematics Subject Classification: 05C85 / 90C27
Key words: Polytope / Steiner 2-edge connected graph / Halin graph.
© EDP Sciences, ROADEF, SMAI, 2008
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.