The 2 edge-disjoint 3-paths polyhedron - Archive ouverte HAL Access content directly
Journal Articles Annals of Telecommunications - annales des télécommunications Year : 2018

The 2 edge-disjoint 3-paths polyhedron

(1) , (2) , (3)


Given an undirected graph, we study the problem of finding K edge-disjoint paths, each one containing at most L edges, between a given pair of nodes. We focus on the case of K = 2 and L = 3. For this particular case, previous known compact formulations are valid only for the case with non-negative edge costs. We provide the first compact linear description that is also valid for general edge costs. We describe new valid inequalities that are added to a well known extended formulation in a layered graph, to get a full description of the polyhedron for K = 2 and L = 3. We use a reduction of the problem to a size-2 stable set problem to prove this second property.
Fichier principal
Vignette du fichier
BFG2016-ANTE-final.pdf (378.24 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01673313 , version 1 (29-12-2017)



Quentin Botton, Bernard Fortz, Luis Gouveia. The 2 edge-disjoint 3-paths polyhedron. Annals of Telecommunications - annales des télécommunications, 2018, 73 (1-2), pp.29-36. ⟨10.1007/s12243-017-0615-2⟩. ⟨hal-01673313⟩
195 View
116 Download



Gmail Facebook Twitter LinkedIn More