The k-edge subgraph problem I: Critical extreme points

Didi Biha, Mohamed; Mahjoub, Ali Ridha

Didi Biha, Mohamed; Mahjoub, Ali Ridha (2004), The k-edge subgraph problem I: Critical extreme points, Linear Algebra and its Applications, 381, p. 117-139. http://dx.doi.org/10.1016/j.laa.2003.11.007

Type

Article accepté pour publication ou publié

Date

2004

Nom de la revue

Linear Algebra and its Applications

Volume

381

Éditeur

Elsevier

Pages

117-139

Résumé (EN)

In this paper we consider the linear relaxation of the k-edge connected subgraph polytope, P(G,k), given by the trivial and the so-called cut inequalities. We introduce an ordering on the fractional extreme points of P(G,k) and describe some structural properties of the minimal extreme points with respect to that ordering. Using this we give sufficient conditions for P(G,k) to be integral.

Mots-clés

Polytope; Cut; k-Edge connected graph; Critical extreme point