The 2 edge-disjoint 3-paths polyhedron

Quentin Botton 1 Bernard Fortz 2 Luis Gouveia 3
2 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - 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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01673313
Contributor : Bernard Fortz <>
Submitted on : Friday, December 29, 2017 - 10:32:59 AM
Last modification on : Friday, March 22, 2019 - 1:36:17 AM

File

BFG2016-ANTE-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

263

Files downloads

88