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
2010Journal name
NetworksVolume
55Number
1Publisher
Wiley Periodicals
Pages
13-32
Publication identifier
Metadata
Show full item recordAuthor(s)
Mailfert, JeanMahjoub, 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 graphRelated items
Showing items related by title and author.
-
Bendali, Fatiha; Ibrahima, Diarrassouba; Didi Biha, Mohamed; Mahjoub, Ali Ridha; Mailfert, Jean (2006) Communication / Conférence
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2021) Document de travail / Working paper
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022) Communication / Conférence
-
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié