Critical extreme points of the 2-edge connected spanning subgraph polytope
Fonlupt, Jean; Mahjoub, Ali Ridha (1999), Critical extreme points of the 2-edge connected spanning subgraph polytope, in Woeginger, Gerhard J.; Burkard, Rainer E.; Cornuejols, Gérard, Integer Programming and Combinatorial Optimization 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings, Springer : Berlin, p. 166-182. http://dx.doi.org/10.1007/3-540-48777-8_13
TypeCommunication / Conférence
Conference title7th International IPCO Conference (IPCO'99)
Book titleInteger Programming and Combinatorial Optimization 7th International IPCO Conference, Graz, Austria, June 9-11, 1999, Proceedings
Book authorWoeginger, Gerhard J.; Burkard, Rainer E.; Cornuejols, Gérard
Series titleLecture Notes in Computer Science
Number of pages453
MetadataShow full item record
Abstract (EN)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 $ \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.
Subjects / KeywordsPolytope; cut; 2-edge connected graph; critical extreme point
Showing items related by title and author.