On the linear relaxation of the 2-node connected subgraph polytope
Mahjoub, Ali Ridha; Nocq, Charles (1999), On the linear relaxation of the 2-node connected subgraph polytope, Discrete Applied Mathematics, 95, 1-3, p. 389-416. http://dx.doi.org/10.1016/S0166-218X(99)00088-8
Type
Article accepté pour publication ou publiéDate
1999Journal name
Discrete Applied MathematicsVolume
95Number
1-3Publisher
Elsevier
Pages
389-416
Publication identifier
Metadata
Show full item recordAbstract (EN)
In this paper, we study the linear relaxation P(G) of the 2-node connected subgraph polytope of a graph G. We introduce an ordering on the fractional extreme points of P(G) and we give a characterization of the minimal extreme points with respect to that ordering. This yields a polynomial method to separate a minimal extreme point of P(G) from the 2-node connected subgraph polytope. It also provides a new class of facet defining inequalities for this polytope.Subjects / Keywords
Cut; Polytopes; Critical extreme point; 2-node connected graphRelated items
Showing items related by title and author.
-
Fonlupt, Jean; Mahjoub, Ali Ridha (2006) Article accepté pour publication ou publié
-
Fonlupt, Jean; Mahjoub, Ali Ridha (1999) Communication / Conférence
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Pesneau, Pierre (2008) Article accepté pour publication ou publié
-
Baïou, Mourad; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié