Show simple item record

dc.contributor.authorPesneau, Pierre
HAL ID: 739311
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorHuygens, David
dc.subjectSurvivable networken
dc.subjectEdge-disjoint pathsen
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.subject.ddclabelPrincipes généraux des mathématiquesen

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record