• 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

The Steiner Traveling Salesman Polytope and Related Polyhedra

Thumbnail
Date
2002
Dewey
Recherche opérationnelle
Sujet
Polyhedral combinatorics; Polytopes; Traveling salesman problem
Journal issue
SIAM Journal on Optimization
Volume
13
Number
2
Publication date
2002
Article pages
498-507
Publisher
SIAM
DOI
http://dx.doi.org/10.1137/S1052623400322287
URI
https://basepub.dauphine.fr/handle/123456789/3915
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Baïou, Mourad
Mahjoub, Ali Ridha
Type
Article accepté pour publication ou publié
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.

  • 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.