Two edge hop-constrained paths and polyhedra
Pesneau, Pierre; Mahjoub, Ali Ridha; Huygens, David (2004), Two edge hop-constrained paths and polyhedra, SIAM journal on Discrete Mathematics, 18, 2, p. 287-314. http://dx.doi.org/10.1137/S0895480102419445
TypeArticle accepté pour publication ou publié
Journal nameSIAM journal on Discrete Mathematics
MetadataShow full item record
Abstract (EN)Given 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).
Subjects / KeywordsSurvivable network; Facet; Polyhedron; Hop-constraints; Edge-disjoint paths
Showing items related by title and author.
The Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cut Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007) Article accepté pour publication ou publié
Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem Diarrassouba, Ibrahima; Gabrel, Virginie; Mahjoub, Ali Ridha; Gouveia, Luis; Pesneau, Pierre (2016) Article accepté pour publication ou publié