The k-edge subgraph problem I: Critical extreme points

dc.contributor.author	Didi Biha, Mohamed HAL ID: 175567
dc.contributor.author	Mahjoub, Ali Ridha
dc.date.accessioned	2010-01-14T11:09:32Z
dc.date.available	2010-01-14T11:09:32Z
dc.date.issued	2004
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/2931
dc.language.iso	en	en
dc.subject	Polytope	en
dc.subject	Cut	en
dc.subject	k-Edge connected graph	en
dc.subject	Critical extreme point	en
dc.subject.ddc	003	en
dc.title	The k-edge subgraph problem I: Critical extreme points	en
dc.type	Article accepté pour publication ou publié
dc.contributor.editoruniversityother	Université de Clermont II;France
dc.contributor.editoruniversityother	Université d’Avignon;France
dc.description.abstracten	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.	en
dc.relation.isversionofjnlname	Linear Algebra and its Applications
dc.relation.isversionofjnlvol	381	en
dc.relation.isversionofjnldate	2004
dc.relation.isversionofjnlpages	117-139	en
dc.relation.isversionofdoi	http://dx.doi.org/10.1016/j.laa.2003.11.007	en
dc.description.sponsorshipprivate	oui	en
dc.relation.isversionofjnlpublisher	Elsevier	en
dc.subject.ddclabel	Recherche opérationnelle	en

Files in this item

Files	Size	Format	View
There are no files associated with this item.