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

Journal name

Linear Algebra and its Applications

Volume

381

Publisher

Elsevier

Pages

117-139

Abstract (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.

Subjects / Keywords

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