Show simple item record

dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorPesneau, Pierre
HAL ID: 739311
dc.date.accessioned2010-03-16T09:55:24Z
dc.date.available2010-03-16T09:55:24Z
dc.date.issued2008
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3707
dc.language.isoenen
dc.subjectHalin graphen
dc.subjectSteiner 2-edge connected graphen
dc.subjectPolytopeen
dc.subject.ddc003en
dc.titleOn the Steiner 2-edge connected subgraph polytopeen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.en
dc.relation.isversionofjnlnameRAIRO
dc.relation.isversionofjnlvol42en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2008-07
dc.relation.isversionofjnlpages259-283en
dc.relation.isversionofdoihttp://dx.doi.org/10.1051/ro:2008022en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherEDP Sciencesen
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record