Show simple item record

Critical extreme points of the 2-edge connected subgraph polytope

dc.contributor.authorFonlupt, Jean
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2009-10-05T09:26:42Z
dc.date.available2009-10-05T09:26:42Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2112
dc.language.isoenen
dc.subjectPolytopeen
dc.subjectCut - 2-edge connected graphen
dc.subjectCritical extreme pointen
dc.subject.ddc519en
dc.titleCritical extreme points of the 2-edge connected subgraph polytopeen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherUniversité Blaise Pascal Clermont II;France
dc.contributor.editoruniversityotherUniversité Pierre et Marie Curie;France
dc.description.abstractenIn this paper we study the extreme points of the polytope P(G), the linear relaxation of the 2-edge connected spanning subgraph polytope of a graph G. We introduce a partial ordering on the extreme points of P(G) and give necessary conditions for a non-integer extreme point of P(G) to be minimal with respect to that ordering. We show that, if X is a non-integer minimal extreme point of P(G), then G and X can be reduced, by means of some reduction operations, to a graph G' and an extreme point X of P(G') where G' and X'satisfy some simple properties. As a consequence we obtain a characterization of the perfectly 2-edge connected graphs, the graphs for which the polytope P(G) is integral.en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol105en
dc.relation.isversionofjnlissue2-3en
dc.relation.isversionofjnldate2006-02
dc.relation.isversionofjnlpages289-310en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10107-005-0654-8en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringer Berlinen
dc.subject.ddclabelProbabilités et mathématiques appliquéesen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record