Skip to Main content Skip to Navigation
Journal articles

The 2 edge-disjoint 3-paths polyhedron

Quentin Botton 1 Bernard Fortz 2 Luis Gouveia 3
2 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Bernard Fortz Connect in order to contact the contributor
Submitted on : Friday, December 29, 2017 - 10:32:59 AM
Last modification on : Tuesday, October 19, 2021 - 12:55:39 PM


Files produced by the author(s)




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