• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2001
Journal name
Discrete Applied Mathematics
Volume
112
Number
1-3
Publisher
Elsevier
Pages
101-120
Publication identifier
http://dx.doi.org/10.1016/S0166-218X(00)00311-5
Metadata
Show full item record
Author(s)
Didi Biha, Mohamed
Kerivin, Hervé
Mahjoub, Ali Ridha
Abstract (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 subgraph

Related items

Showing items related by title and author.

  • Thumbnail
    On the Polytope of the (1,2)-Survivable Network Design Problem 
    Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié
  • Thumbnail
    Une approche polyédrale pour le problème de l'arbre Steiner 
    Didi Biha, Mohamed; Kerivin, Hervé; Mahjoub, Ali Ridha (1998) Communication / Conférence
  • Thumbnail
    Steiner k-edge connected subgraph polyhedra 
    Didi Biha, Mohamed; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
  • Thumbnail
    k-Edge connected polyhedra on series-parallel graphs 
    Didi Biha, Mohamed; Mahjoub, Ali Ridha (1996) Article accepté pour publication ou publié
  • Thumbnail
    A Branch-and-Cut algorithm for the k-edge connected subgraph problem 
    Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo