The 2 edge-disjoint 3-paths polyhedron

Botton, Quentin; Fortz, Bernard; Gouveia, Luis

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1007/s12243-017-0615-2

Titre :

The 2 edge-disjoint 3-paths polyhedron

Auteur(s) :

Botton, Quentin [Auteur]
Université Catholique de Louvain = Catholic University of Louvain [UCL]
Fortz, Bernard [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Gouveia, Luis [Auteur]
Universidade de Lisboa = University of Lisbon = Université de Lisbonne [ULISBOA]

Titre de la revue :

Annals of Telecommunications - annales des télécommunications

Pagination :

29–36

Éditeur :

Springer

Date de publication :

2018

ISSN :

0003-4347

Mot(s)-clé(s) en anglais :

Hop constraints
Survivability
Network design
Combinatorial Optimization

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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, ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :