dc.contributor.author Fonlupt, Jean dc.contributor.author Mahjoub, Ali Ridha dc.date.accessioned 2009-10-05T09:26:42Z dc.date.available 2009-10-05T09:26:42Z dc.date.issued 2006 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/2112 dc.language.iso en en dc.subject Polytope en dc.subject Cut - 2-edge connected graph en dc.subject Critical extreme point en dc.subject.ddc 519 en dc.title Critical extreme points of the 2-edge connected subgraph polytope en dc.type Article accepté pour publication ou publié dc.contributor.editoruniversityother Université Blaise Pascal Clermont II;France dc.contributor.editoruniversityother Université Pierre et Marie Curie;France dc.description.abstracten In 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.isversionofjnlname Mathematical Programming dc.relation.isversionofjnlvol 105 en dc.relation.isversionofjnlissue 2-3 en dc.relation.isversionofjnldate 2006-02 dc.relation.isversionofjnlpages 289-310 en dc.relation.isversionofdoi http://dx.doi.org/10.1007/s10107-005-0654-8 en dc.description.sponsorshipprivate oui en dc.relation.isversionofjnlpublisher Springer Berlin en dc.subject.ddclabel Probabilités et mathématiques appliquées en
﻿

## Files in this item

FilesSizeFormatView

There are no files associated with this item.