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
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
Abstract (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 / KeywordsCut; Polytopes; Critical extreme point; 2-node connected graph
Showing items related by title and author.
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié