Critical extreme points of the 2-edge connected subgraph polytope
Fonlupt, Jean; Mahjoub, Ali Ridha (2006), Critical extreme points of the 2-edge connected subgraph polytope, Mathematical Programming, 105, 2-3, p. 289-310. http://dx.doi.org/10.1007/s10107-005-0654-8
TypeArticle accepté pour publication ou publié
Journal nameMathematical Programming
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 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.
Subjects / KeywordsPolytope; Cut - 2-edge connected graph; Critical extreme point
Showing items related by title and author.