Voir la notice de l'article provenant de la source Numdam
In this paper, we study the Steiner -edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner -partition inequalities, that generalizes the so-called Steiner -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 -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 -edge cutsets. And we show that the generalized Steiner -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 -edge connected subgraph problem in that class of graphs.
@article{RO_2008__42_3_259_0,
author = {Mahjoub, A. Rhida and Pesneau, Pierre},
title = {On the {Steiner} $2$-edge connected subgraph polytope},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {259--283},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ro:2008022},
mrnumber = {2444486},
zbl = {1157.05049},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2008022/}
}
TY - JOUR AU - Mahjoub, A. Rhida AU - Pesneau, Pierre TI - On the Steiner $2$-edge connected subgraph polytope JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 259 EP - 283 VL - 42 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro:2008022/ DO - 10.1051/ro:2008022 LA - en ID - RO_2008__42_3_259_0 ER -
%0 Journal Article %A Mahjoub, A. Rhida %A Pesneau, Pierre %T On the Steiner $2$-edge connected subgraph polytope %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 259-283 %V 42 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro:2008022/ %R 10.1051/ro:2008022 %G en %F RO_2008__42_3_259_0
Mahjoub, A. Rhida; Pesneau, Pierre. On the Steiner $2$-edge connected subgraph polytope. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 259-283. doi: 10.1051/ro:2008022
Cité par Sources :