Show simple item record

dc.contributor.authorBendali, Fatiha
HAL ID: 172499
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorMailfert, Jean
HAL ID: 20286
dc.contributor.authorDiarrassouba, Ibrahima
HAL ID: 745402
dc.date.accessioned2011-03-23T14:53:13Z
dc.date.available2011-03-23T14:53:13Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5806
dc.language.isoenen
dc.subjectSurvivable networken
dc.subjectEdge-disjoint pathsen
dc.subjectHop-constrained pathsen
dc.subjectFlowen
dc.subjectPolytopeen
dc.subjectFaceten
dc.subject.ddc511en
dc.titleThe k edge-disjoint 3-hop-constrained paths polytopeen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherLaboratoire LIMOS, CNRS UMR 6158, Université d’Auvergne;France
dc.contributor.editoruniversityotherLaboratoire LIMOS, CNRS UMR 6158, Université Blaise Pascal-Clermont II;France
dc.description.abstractenGiven a graph G with two distinguished nodes s and t, a cost on each edge of G and two fixed integers k≥2, L≥2, the k edge-disjoint L-hop-constrained paths problem is to find a minimum cost subgraph of G such that between s and t there are at least k edge-disjoint paths of length at most L. In this paper we consider this problem from a polyhedral point of view. We give an integer programming formulation for the problem and discuss the associated polytope. In particular, we show that when L=3 and k≥2, the linear relaxation of the associated polytope, given by the trivial, the st-cut and the so-called L-path-cut inequalities, is integral. As a consequence, we obtain a polynomial time cutting plane algorithm for the problem when L=2,3 and k≥1. This generalizes the results of Huygens et al. (2004) [1] for k=2 and L=2,3 and those of Dahl et al. (2006) [2] for L=2 and k≥2. This also proves a conjecture in [1].en
dc.relation.isversionofjnlnameDiscrete Optimization
dc.relation.isversionofjnlvol7en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages222-233en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.disopt.2010.05.001en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record