The 2 edge-disjoint 3-paths polyhedron

Botton, Quentin; Fortz, Bernard; Gouveia, Luis

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1007/s12243-017-0615-2

Title :

The 2 edge-disjoint 3-paths polyhedron

Author(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]

Journal title :

Annals of Telecommunications - annales des télécommunications

Pages :

29–36

Publisher :

Springer

Publication date :

2018

ISSN :

0003-4347

English keyword(s) :

Hop constraints
Survivability
Network design
Combinatorial Optimization

HAL domain(s) :

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

English abstract : [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, ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

Collections :