On the linear relaxation of the 2-node connected  subgraph polytope

Mahjoub, Ali Ridha; Nocq, Charles

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

1999

Journal name

Discrete Applied Mathematics

Volume

Number

1-3

Publisher

Elsevier

Pages

389-416

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 / Keywords

Cut; Polytopes; Critical extreme point; 2-node connected graph