The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016), The k-node connected subgraph problem: Polyhedral analysis and Branch-and-Cut, Electronic Notes in Discrete Mathematics, 52, p. 117-124. 10.1016/j.endm.2016.03.016
Type
Article accepté pour publication ou publiéDate
2016Journal name
Electronic Notes in Discrete MathematicsVolume
52Publisher
Elsevier
Pages
117-124
Publication identifier
Metadata
Show full item recordAuthor(s)
Diarrassouba, IbrahimaLaboratoire de Mathématiques Appliquées du Havre [LMAH]
Mahjoub, Meriem
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]
Taktak, Raouia
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper we consider the k-node connected subgraph problem. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We introduce further classes of valid inequalities and discuss their facial aspect. We also devise separation routines and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using those results, we devise a Branch-and-Cut algorithm and present some preliminary computational results.Subjects / Keywords
k-node connected graph; polytope; separation; branch-and-cutRelated items
Showing items related by title and author.
-
Mahjoub, Meriem; Diarrassouba, Ibrahima; Mahjoub, Ali Ridha; Taktak, Raouia (2017) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Yaman, Hande (2016) Article accepté pour publication ou publié
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
-
Diarrassouba, Ibrahima; Hadhbi, Youssouf; Mahjoub, Ali Ridha (2022) Communication / Conférence
-
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié