• 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

A Branch-and-Cut algorithm for the k-edge connected subgraph problem

Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010), A Branch-and-Cut algorithm for the k-edge connected subgraph problem, Networks, 55, 1, p. 13-32. http://dx.doi.org/10.1002/net.20310

Type
Article accepté pour publication ou publié
Date
2010
Journal name
Networks
Volume
55
Number
1
Publisher
Wiley Periodicals
Pages
13-32
Publication identifier
http://dx.doi.org/10.1002/net.20310
Metadata
Show full item record
Author(s)
Mailfert, Jean
Mahjoub, Ali Ridha
Didi Biha, Mohamed
Ibrahima, Diarrassouba
Bendali, Fatiha
Abstract (EN)
In this article, we consider the k-edge connected subgraph problem from a polyhedral point of view. We introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we develop a Branch-and-Cut algorithm and present some computational results.
Subjects / Keywords
Reduction operations; Branch-and-cut; Separation; Facet; Polytope; K-edge connected graph

Related items

Showing items related by title and author.

  • Thumbnail
    Un algorithme de coupes et branchements pour le problème du sous graphe k-arête connexe 
    Bendali, Fatiha; Ibrahima, Diarrassouba; Didi Biha, Mohamed; Mahjoub, Ali Ridha; Mailfert, Jean (2006) Communication / Conférence
  • Thumbnail
    The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut 
    Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
  • Thumbnail
    Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem 
    Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
  • Thumbnail
    Polyhedral Investigation and Branch-and-Cut Algorithm for the Spectrum Assignment Problem 
    Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022) Communication / Conférence
  • Thumbnail
    The survivable k-node-connected network design problem: Valid inequalities and Branch-and-Cut 
    Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) 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