• 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

Separation of partition inequalities for the (1,2)-survivable network design problem

Thumbnail
Date
2002
Dewey
Recherche opérationnelle
Sujet
Separation algorithm; Submodular function; Partition inequalities; Survivable network
Journal issue
Operations Research Letters
Volume
30
Number
4
Publication date
08-2002
Article pages
265-268
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/S0167-6377(02)00182-7
URI
https://basepub.dauphine.fr/handle/123456789/3917
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Kerivin, Hervé
Mahjoub, Ali Ridha
Type
Article accepté pour publication ou publié
Abstract (EN)
Given a graph G=(V,E) with edge costs and an integer vector Image associated with the nodes of V, the survivable network design problem is to find a minimum cost subgraph of G such that between every pair of nodes s,t of V, there are at least min{r(s),r(t)} edge-disjoint paths. In this paper we consider that problem when rset membership, variant{1,2}V. This case is of particular interest to the telecommunication industry. We show that the separation problem for the so-called partition inequalities reduces to minimizing a submodular function. This yields a polynomial time separation algorithm for these inequalities in that case.

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