• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Steiner Trees and Polyhedra

Thumbnail
Date
2001
Dewey
Probabilités et mathématiques appliquées
Sujet
Series–parallel graph; Steiner connected subgraph
Journal issue
Discrete Applied Mathematics
Volume
112
Number
1-3
Publication date
2001
Article pages
101-120
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/S0166-218X(00)00311-5
URI
https://basepub.dauphine.fr/handle/123456789/1589
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Didi Biha, Mohamed
Kerivin, Hervé
Mahjoub, Ali Ridha
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.