Back to Search
Start Over
Critical Extreme Points of the 2-Edge Connected Spannning Subgraph Polytope.
- Source :
- Integer Programming & Combinatorial Optimization (9783540660194); 1999, p166-182, 17p
- Publication Year :
- 1999
-
Abstract
- 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$$ is a non-integer minimal extreme point of P(G), then G and $$ \bar x$$ can be reduced, by means of some reduction operations, to a graph G′ and an extreme point $$ \bar x'$$ of P(G′) where G′ and $$ \bar 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540660194
- Database :
- Supplemental Index
- Journal :
- Integer Programming & Combinatorial Optimization (9783540660194)
- Publication Type :
- Book
- Accession number :
- 33100508
- Full Text :
- https://doi.org/10.1007/3-540-48777-8_13