Thumbnail - Request a copy

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
2016
Journal name
Electronic Notes in Discrete Mathematics
Volume
52
Publisher
Elsevier
Pages
117-124
Publication identifier
Metadata
Show full item record
Author(s)
Diarrassouba, Ibrahima
Laboratoire 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-cut