• 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

On Survivable Network Polyhedra

Thumbnail
Date
2005
Dewey
Probabilités et mathématiques appliquées
Sujet
Polynomial algorithm; Series–parallel graph; Cut; Polyhedron; Survivable network
Journal issue
Discrete Mathematics
Volume
290
Number
2-3
Publication date
2005
Article pages
183-210
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.disc.2004.08.017
URI
https://basepub.dauphine.fr/handle/123456789/2115
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Mahjoub, Ali Ridha
Kerivin, Hervé
Type
Article accepté pour publication ou publié
Abstract (EN)
Given an undirected network G=(V,E), a vector of nonnegative integers r=(r(v):v E v) associated with the nodes of G and weights on the edges of G, the survivable network design problem is to determine a minimum-weight subnetwork of G such that between every two nodes u, v of V, there are at least min{r(u),r(v)} edge-disjoint paths. In this paper we study the polytope associated with the solutions to that problem. We show that when the underlying network is series–parallel and r(v) is even for all v E v, the polytope is completely described by the trivial constraints and the so-called cut constraints. As a consequence, we obtain a polynomial time algorithm for the survivable network design problem in that class of networks. This generalizes and unifies known results in the literature. We also obtain a linear description of the polyhedron associated with the problem in the same class of networks when the use of more than one copy of an edge is allowed.

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