The k-edge subgraph problem I: Critical extreme points
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
2004Journal name
Linear Algebra and its ApplicationsVolume
381Publisher
Elsevier
Pages
117-139
Publication identifier
Metadata
Show full item recordAbstract (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 pointRelated items
Showing items related by title and author.
-
Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
-
Fonlupt, Jean; Mahjoub, Ali Ridha (2006) Article accepté pour publication ou publié
-
Fonlupt, Jean; Mahjoub, Ali Ridha (1999) Communication / Conférence
-
Didi Biha, Mohamed; Mahjoub, Ali Ridha (2000) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié