• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

On minimal two-edge-connected graphs

Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha (2014), On minimal two-edge-connected graphs, 2014 International Conference on Control, Decision and Information Technologies (CoDIT). Proceedings, IEEE : Piscataway, NJ, p. 251-256. 10.1109/CoDIT.2014.6996902

Type
Communication / Conférence
Date
2014
Conference title
2014 International Conference on Control, Decision and Information Technologies (CoDIT)
Conference date
2014-11
Conference city
Metz
Conference country
France
Book title
2014 International Conference on Control, Decision and Information Technologies (CoDIT). Proceedings
Publisher
IEEE
Published in
Piscataway, NJ
ISBN
978-1-4799-6773-5
Pages
251-256
Publication identifier
10.1109/CoDIT.2014.6996902
Metadata
Show full item record
Author(s)
Cornaz, Denis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Magnouche, Youcef
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.
Subjects / Keywords
Two-edge-connected; branch-and-cut; polyhedral approach; separation problem

Related items

Showing items related by title and author.

  • Thumbnail
    The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut 
    Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
  • Thumbnail
    The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut 
    Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2015) Communication / Conférence
  • Thumbnail
    On perfectly two-edge connected graphs 
    Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié
  • Thumbnail
    Minimal arc-sets spanning dicycles 
    Cornaz, Denis; Kerivin, Hervé; Mahjoub, Ali Ridha (2018) Article accepté pour publication ou publié
  • Thumbnail
    Two edge connected spanning subgraphs and polyhedra 
    Mahjoub, Ali Ridha (1994) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo