Show simple item record

dc.contributor.authorPesneau, Pierre
HAL ID: 739311
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorHuygens, David
dc.date.accessioned2009-09-09T09:05:30Z
dc.date.available2009-09-09T09:05:30Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/1523
dc.language.isoenen
dc.subjectSurvivable networken
dc.subjectFaceten
dc.subjectPolyhedronen
dc.subjectHop-constraintsen
dc.subjectEdge-disjoint pathsen
dc.subject.ddc511en
dc.titleTwo edge hop-constrained paths and polyhedraen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherLaboratory of Applied Physical Chemistry ISOFYS Ghent University;Belgique
dc.contributor.editoruniversityotherUniversité Sciences et Technologies - Bordeaux I – Université Victor Segalen - Bordeaux II;France
dc.description.abstractenGiven a graph G with distinguished nodes s and t, a cost on each edge of G, and a fixed integer L \geq 2, the two edge-disjoint hop-constrained paths problem is to find a minimum cost subgraph such that between s and t there exist at least two edge-disjoint paths of length at most L. In this paper, we consider that problem from a polyhedral point of view. We give an integer programming formulation for the problem when L = 2,3. An extension of this result to the more general case where the number of required paths is arbitrary and L = 2,3 is also given. We discuss the associated polytope, P(G,L), for L = 2,3. In particular, we show in this case that the linear relaxation of P(G,L), Q(G,L), 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. We also give necessary and sufficient conditions for these inequalities to define facets of P(G,L) for L \geq 2 when G is complete. We finally investigate the dominant of P(G,L) and give a complete description of this polyhedron for L \geq 2 when P(G,L) = Q(G,L).en
dc.relation.isversionofjnlnameSIAM journal on Discrete Mathematics
dc.relation.isversionofjnlvol18en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2004
dc.relation.isversionofjnlpages287-314en
dc.relation.isversionofdoihttp://dx.doi.org/10.1137/S0895480102419445en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSiamen
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