On minimal two-edge-connected graphs

Thumbnail
Date
2014
Indexation documentaire
Recherche opérationnelle
Subject
Two-edge-connected; branch-and-cut; polyhedral approach; separation problem
Réf version publiée
http://dx.doi.org/10.1109/CoDIT.2014.6996902
Titre du colloque
2014 International Conference on Control, Decision and Information Technologies (CoDIT)
Date du colloque
11-2014
Ville du colloque
Metz
Pays du colloque
France
Titre de l'ouvrage
2014 International Conference on Control, Decision and Information Technologies (CoDIT). Proceedings
Nom de l'éditeur
IEEE
Ville de l'éditeur
Piscataway, NJ
Année
2014
ISBN
978-1-4799-6773-5
URI
https://basepub.dauphine.fr/handle/123456789/15664
Collections
Métadonnées
Afficher la notice complète
Auteur
Cornaz, Denis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Magnouche, Youcef
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Nombre de pages du document
251-256
Résumé en anglais
Given G = (V;E) an undirected graph and a nonnegative cost function c : E → ℚ, the 2-edge connected spanning subgraph problem (TECSP for short) is to find a two-edge connected subgraph HP = (V; F) of G with minimum cost (i.e., c(F) = Σe∈F c(e) is minimum). If c(e) > 0 for all e ∈ E then every optimal solution for TECSP is an inclusionwise minimal two-edge connected subgraph. In this paper we provide preliminary results, from a polyhedral point of view, concerning the inclusionwise minimal solutions of TECSP. This problem is clearly NP-Hard. We propose an ILP formulation for the problem and study the associated polytope for the wheels. Morever, we describe some valid inequalities and propose a branch-and-cut algorithm for the problem.