Steiner Trees and Polyhedra
Didi Biha, Mohamed; Kerivin, Hervé; Mahjoub, Ali Ridha (2001), Steiner Trees and Polyhedra, Discrete Applied Mathematics, 112, 1-3, p. 101-120. http://dx.doi.org/10.1016/S0166-218X(00)00311-5
Type
Article accepté pour publication ou publiéDate
2001Journal name
Discrete Applied MathematicsVolume
112Number
1-3Publisher
Elsevier
Pages
101-120
Publication identifier
Metadata
Show full item recordAbstract (EN)
In 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.Subjects / Keywords
Series–parallel graph; Steiner connected subgraphRelated items
Showing items related by title and author.
-
Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Kerivin, Hervé; Mahjoub, Ali Ridha (1998) Communication / Conférence
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (1996) Article accepté pour publication ou publié
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié