Show simple item record

dc.contributor.authorDidi Biha, Mohamed
HAL ID: 175567
dc.contributor.authorKerivin, Hervé
dc.contributor.authorMahjoub, Ali Ridha
dc.subjectSeries–parallel graphen
dc.subjectSteiner connected subgraphen
dc.titleSteiner Trees and Polyhedraen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherEcole Polytechnique, Montréal;Canada
dc.contributor.editoruniversityotherUniversité de Clermont II;France
dc.description.abstractenIn this paper we study the dominant of the Steiner tree polytope. We introduce a new class of valid inequalities that generalizes the so-called odd hole, wheel, bipartite, anti-hole and Steiner partition inequalities introduced by Chopra and Rao (Math. Programming 64 (1994) 209–229, 231–246), and we give sufficient conditions for these inequalities to define facets. We describe some procedures that permit to construct facets from known ones for the dominant of the Steiner tree polytope and the closely related Steiner connected subgraph polytope. Using these methods we give a counterexample to a conjecture of Chopra and Rao on the dominant of the Steiner tree polytope on 2-trees. We also describe the dominant of the Steiner tree polytope and the Steiner connected subgraph polytope on special classes of graphs. In particular, we show that if the underlying graph is series–parallel and the terminals satisfy certain conditions, then both polyhedra are given by the trivial inequalities and the Steiner partition inequalities.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.subject.ddclabelProbabilités et mathématiques appliquéesen

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record