The 2 edge-disjoint 3-paths polyhedron - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Annals of Telecommunications - annales des télécommunications Année : 2018

The 2 edge-disjoint 3-paths polyhedron

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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⟩
198 Consultations
133 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More