Show simple item record

Critical extreme points of the 2-edge connected spanning subgraph polytope

dc.contributor.authorFonlupt, Jean
dc.contributor.authorMahjoub, Ali Ridha
dc.date.accessioned2011-04-04T12:58:11Z
dc.date.available2011-04-04T12:58:11Z
dc.date.issued1999
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5882
dc.language.isoenen
dc.subjectPolytopeen
dc.subjectcuten
dc.subject2-edge connected graphen
dc.subjectcritical extreme pointen
dc.subject.ddc003en
dc.titleCritical extreme points of the 2-edge connected spanning subgraph polytopeen
dc.typeCommunication / Conférence
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 $ \bar x$x is a non-integer minimal extreme point of P(G), then G and $ \bar x$x can be reduced, by means of some reduction operations, to a graph G′ and an extreme point $ \bar x'$x of P(G′) where G′ and $ \bar x'$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.identifier.citationpages166-182en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber1610
dc.relation.ispartoftitleInteger Programming and Combinatorial Optimization 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedingsen
dc.relation.ispartofeditorWoeginger, Gerhard J.
dc.relation.ispartofeditorBurkard, Rainer E.
dc.relation.ispartofeditorCornuejols, Gérard
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate1999
dc.relation.ispartofpages453en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/3-540-48777-8en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-66019-4en
dc.relation.conftitle7th International IPCO Conference (IPCO'99)en
dc.relation.confdate1999-06
dc.relation.confcityGrazen
dc.relation.confcountryAutricheen
dc.identifier.doihttp://dx.doi.org/10.1007/3-540-48777-8_13


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