• 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

The Steiner Traveling Salesman Polytope and Related Polyhedra

Baïou, Mourad; Mahjoub, Ali Ridha (2002), The Steiner Traveling Salesman Polytope and Related Polyhedra, SIAM Journal on Optimization, 13, 2, p. 498-507. http://dx.doi.org/10.1137/S1052623400322287

Type
Article accepté pour publication ou publié
Date
2002
Journal name
SIAM Journal on Optimization
Volume
13
Number
2
Publisher
SIAM
Pages
498-507
Publication identifier
http://dx.doi.org/10.1137/S1052623400322287
Metadata
Show full item record
Author(s)
Baïou, Mourad
Mahjoub, Ali Ridha
Abstract (EN)
In this paper we consider an extended formulation of the Steiner traveling salesman problem, that is, when variables are associated with both the edges and the nodes of the graph. We give a complete linear description of the associated polytope when the underlying graph is series-parallel. By projecting this polytope onto the edge variables, we obtain a characterization of the Steiner traveling salesman polytope in the same class of graphs. Both descriptions yield polynomial time (cutting plane) algorithms for the corresponding problems in that class of graphs.
Subjects / Keywords
Polyhedral combinatorics; Polytopes; Traveling salesman problem

Related items

Showing items related by title and author.

  • Thumbnail
    Steiner 2-edge connected subgraph polytopes on series-parallel graphs 
    Baïou, Mourad; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié
  • Thumbnail
    Partition Inequalities: Separation, Extensions and Network Design, 
    Mahjoub, Ali Ridha; Barahona, Francisco; Baïou, Mourad (2011) Chapitre d'ouvrage
  • Thumbnail
    Separating Partition Inequalities 
    Baïou, Mourad; Barahona, Francisco; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
  • Thumbnail
    Compositions of Graphs and the Triangle-Free Subgraph Polytope 
    Bendali, Fatiha; Mailfert, Jean; Mahjoub, Ali Ridha (2002) Article accepté pour publication ou publié
  • Thumbnail
    One-node cutsets and the dominating set polytope 
    Bouchakour, Mustapha; Mahjoub, Ali Ridha (1997) 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